product iamge

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

This document was uploaded by one of our users. The uploader already confirmed that they had the permission to publish it. If you are author/publisher or own the copyright of this documents, please report to us by using this DMCA report form.

Download
Search on Amazon

Simply click on the Download Book button.

Yes, Book downloads on Ebookily are 100% Free.

Sometimes the book is free on Amazon As well, so go ahead and hit "Search on Amazon"

This book constitutes the joint refereed proceedings of the 7th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2004 and the 8th International Workshop on Randomization and Computation, RANDOM 2004, held in Cambridge, MA, USA in August 2004.

The 37 revised full papers presented were carefully reviewed and selected from 87 submissions. Among the issues addressed are design and analysis of approximation algorithms, inapproximability results, approximation classes, online problems, graph algorithms, cuts, geometric computations, network design and routing, packing and covering, scheduling, game theory, design and analysis of randomised algorithms, randomized complexity theory, pseudorandomness, derandomization, probabilistic proof systems, error-correcting codes, and other applications of approximation and randomness.

Author(s): Mansoor Alicherry, Randeep Bhatia, Yung-Chun (Justin) Wan (auth.), Klaus Jansen, Sanjeev Khanna, José D. P. Rolim, Dana Ron (eds.)
Series: Lecture Notes in Computer Science 3122
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 2004

Language: English
Pages: 434
Tags: Algorithm Analysis and Problem Complexity; Discrete Mathematics in Computer Science; Numeric Computing; Algorithms

Front Matter....Pages -
Designing Networks with Existing Traffic to Support Fast Restoration....Pages 1-12
Simultaneous Source Location....Pages 13-26
Computationally-Feasible Truthful Auctions for Convex Bundles....Pages 27-38
Randomized Approximation Algorithms for Set Multicover Problems with Applications to Reverse Engineering of Protein and Gene Networks....Pages 39-50
On the Crossing Spanning Tree Problem....Pages 51-60
A 3/4-Approximation Algorithm for Maximum ATSP with Weights Zero and One....Pages 61-71
Maximum Coverage Problem with Group Budget Constraints and Applications....Pages 72-83
The Greedy Algorithm for the Minimum Common String Partition Problem....Pages 84-95
Approximating Additive Distortion of Embeddings into Line Metrics....Pages 96-104
Polylogarithmic Inapproximability of the Radio Broadcast Problem....Pages 105-116
On Systems of Linear Equations with Two Variables per Equation....Pages 117-127
An Auction-Based Market Equilibrium Algorithm for the Separable Gross Substitutability Case....Pages 128-138
Cost-Sharing Mechanisms for Network Design....Pages 139-150
Approximating Max k CSP Using Random Restrictions....Pages 151-162
Approximation Schemes for Broadcasting in Heterogenous Networks....Pages 163-170
Centralized Deterministic Broadcasting in Undirected Multi-hop Radio Networks....Pages 171-182
Convergence Issues in Competitive Games....Pages 183-194
Cuts and Orderings: On Semidefinite Relaxations for the Linear Ordering Problem....Pages 195-206
Min-Max Multiway Cut....Pages 207-218
The Chromatic Number of Random Regular Graphs....Pages 219-228
Estimating the Distance to a Monotone Function....Pages 229-236
Edge Coloring with Delays....Pages 237-248
Small Pseudo-random Families of Matrices: Derandomizing Approximate Quantum Encryption....Pages 249-260
The Sketching Complexity of Pattern Matching....Pages 261-272
Non-Abelian Homomorphism Testing, and Distributions Close to Their Self-convolutions....Pages 273-285
Robust Locally Testable Codes and Products of Codes....Pages 286-297
A Stateful Implementation of a Random Function Supporting Parity Queries over Hypercubes....Pages 298-309
Strong Refutation Heuristics for Random k -SAT....Pages 310-321
Counting Connected Graphs and Hypergraphs via the Probabilistic Method....Pages 322-333
Improved Randomness Extraction from Two Independent Sources....Pages 334-344
The Diameter of Randomly Perturbed Digraphs and Some Applications....Pages 345-356
Maximum Weight Independent Sets and Matchings in Sparse Random Graphs....Pages 357-368
Estimating Frequency Moments of Data Streams Using Random Linear Combinations....Pages 369-380
Fooling Parity Tests with Parity Gates....Pages 381-392
Distribution-Free Connectivity Testing....Pages 393-404
Testing the Independence Number of Hypergraphs....Pages 405-416
A Note on Approximate Counting for k -DNF....Pages 417-425
Back Matter....Pages -