Approximation, randomization, and combinatorial optimization : algorithms and techniques : 7th International W | International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (7th : 2004 : Cambridge, Mass.), Jansen, Klaus, International Workshop on Randomization and Approximation Techniques in Computer Science (8th : 2004 : Cambridge, Mass.)

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques: 7th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2004, and 8th International Workshop on Randomization and Computation, RANDOM 2004, Cambridge, MA, USA, August 22-24, 2004. Proceedings
Author: Klaus Jansen, Sanjeev Khanna, José D. P. Rolim, Dana Ron
Published by Springer Berlin Heidelberg
ISBN: 978-3-540-22894-3
DOI: 10.1007/b99805

Table of Contents:

• Designing Networks with Existing Traffic to Support Fast Restoration
• Simultaneous Source Location
• Computationally-Feasible Truthful Auctions for Convex Bundles
• Randomized Approximation Algorithms for Set Multicover Problems with Applications to Reverse Engineering of Protein and Gene Networks
• On the Crossing Spanning Tree Problem
• A 3/4-Approximation Algorithm for Maximum ATSP with Weights Zero and One
• Maximum Coverage Problem with Group Budget Constraints and Applications
• The Greedy Algorithm for the Minimum Common String Partition Problem
• Approximating Additive Distortion of Embeddings into Line Metrics
• Polylogarithmic Inapproximability of the Radio Broadcast Problem
• On Systems of Linear Equations with Two Variables per Equation
• An Auction-Based Market Equilibrium Algorithm for the Separable Gross Substitutability Case
• Cost-Sharing Mechanisms for Network Design
• Approximating Max
• Approximation Schemes for Broadcasting in Heterogenous Networks
• Centralized Deterministic Broadcasting in Undirected Multi-hop Radio Networks
• Convergence Issues in Competitive Games
• Cuts and Orderings: On Semidefinite Relaxations for the Linear Ordering Problem
• Min-Max Multiway Cut
• The Chromatic Number of Random Regular Graphs

Includes bibliographical references and index