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. ProceedingsAuthor: Klaus Jansen, Sanjeev Khanna, José D. P. Rolim, Dana Ron Published by Springer Berlin Heidelberg ISBN: 978-3-540-22894-3 DOI: 10.1007/b99805Table 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