8. RANDOM / 7. APPROX 2004: Cambridge, MA, USA

Klaus Jansen, Sanjeev Khanna, José D. P. Rolim, Dana Ron (Eds.): 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. Lecture Notes in Computer Science 3122 Springer 2004, ISBN 3-540-22894-2 BibTeX

Contributed Talks of APPROX

Mansoor Alicherry, Randeep Bhatia, Yung-Chun (Justin) Wan:
Designing Networks with Existing Traffic to Support Fast Restoration. 1-12
Electronic Edition (link) BibTeX
Konstantin Andreev, Charles Garrod, Bruce M. Maggs, Adam Meyerson:
Simultaneous Source Location. 13-26
Electronic Edition (link) BibTeX
Moshe Babaioff, Liad Blumrosen:
Computationally-Feasible Truthful Auctions for Convex Bundles. 27-38
Electronic Edition (link) BibTeX
Piotr Berman, Bhaskar DasGupta, Eduardo D. Sontag:
Randomized Approximation Algorithms for Set Multicover Problems with Applications to Reverse Engineering of Protein and Gene Networks. 39-50
Electronic Edition (link) BibTeX
Vittorio Bilò, Vineet Goyal, R. Ravi, Mohit Singh:
On the Crossing Spanning Tree Problem. 51-60
Electronic Edition (link) BibTeX
Markus Bläser:
A 3/4-Approximation Algorithm for Maximum ATSP with Weights Zero and One. 61-71
Electronic Edition (link) BibTeX
Chandra Chekuri, Amit Kumar:
Maximum Coverage Problem with Group Budget Constraints and Applications. 72-83
Electronic Edition (link) BibTeX
Marek Chrobak, Petr Kolman, Jiri Sgall:
The Greedy Algorithm for the Minimum Common String Partition Problem. 84-95
Electronic Edition (link) BibTeX
Kedar Dhamdhere:
Approximating Additive Distortion of Embeddings into Line Metrics. 96-104
Electronic Edition (link) BibTeX
Michael Elkin, Guy Kortsarz:
Polylogarithmic Inapproximability of the Radio Broadcast Problem. 105-116
Electronic Edition (link) BibTeX
Uriel Feige, Daniel Reichman:
On Systems of Linear Equations with Two Variables per Equation. 117-127
Electronic Edition (link) BibTeX
Rahul Garg, Sanjiv Kapoor, Vijay V. Vazirani:
An Auction-Based Market Equilibrium Algorithm for the Separable Gross Substitutability Case. 128-138
Electronic Edition (link) BibTeX
Anupam Gupta, Aravind Srinivasan, Éva Tardos:
Cost-Sharing Mechanisms for Network Design. 139-150
Electronic Edition (link) BibTeX
Gustav Hast:
Approximating Max kCSP Using Random Restrictions. 151-162
Electronic Edition (link) BibTeX
Samir Khuller, Yoo Ah Kim, Gerhard J. Woeginger:
Approximation Schemes for Broadcasting in Heterogenous Networks. 163-170
Electronic Edition (link) BibTeX
Dariusz R. Kowalski, Andrzej Pelc:
Centralized Deterministic Broadcasting in Undirected Multi-hop Radio Networks. 171-182
Electronic Edition (link) BibTeX
Vahab S. Mirrokni, Adrian Vetta:
Convergence Issues in Competitive Games. 183-194
Electronic Edition (link) BibTeX
Alantha Newman:
Cuts and Orderings: On Semidefinite Relaxations for the Linear Ordering Problem. 195-206
Electronic Edition (link) BibTeX
Zoya Svitkina, Éva Tardos:
Min-Max Multiway Cut. 207-218
Electronic Edition (link) BibTeX

Contributed Talks of RANDOM

Dimitris Achlioptas, Cristopher Moore:
The Chromatic Number of Random Regular Graphs. 219-228
Electronic Edition (link) BibTeX
Nir Ailon, Bernard Chazelle, Seshadhri Comandur, Ding Liu:
Estimating the Distance to a Monotone Function. 229-236
Electronic Edition (link) BibTeX
Noga Alon, Vera Asodi:
Edge Coloring with Delays. 237-248
Electronic Edition (link) BibTeX
Andris Ambainis, Adam Smith:
Small Pseudo-random Families of Matrices: Derandomizing Approximate Quantum Encryption. 249-260
Electronic Edition (link) BibTeX
Ziv Bar-Yossef, T. S. Jayram, Robert Krauthgamer, Ravi Kumar:
The Sketching Complexity of Pattern Matching. 261-272
Electronic Edition (link) BibTeX
Michael Ben-Or, Don Coppersmith, Michael Luby, Ronitt Rubinfeld:
Non-Abelian Homomorphism Testing, and Distributions Close to Their Self-convolutions. 273-285
Electronic Edition (link) BibTeX
Eli Ben-Sasson, Madhu Sudan:
Robust Locally Testable Codes and Products of Codes. 286-297
Electronic Edition (link) BibTeX
Andrej Bogdanov, Hoeteck Wee:
A Stateful Implementation of a Random Function Supporting Parity Queries over Hypercubes. 298-309
Electronic Edition (link) BibTeX
Amin Coja-Oghlan, Andreas Goerdt, André Lanka:
Strong Refutation Heuristics for Random k-SAT. 310-321
Electronic Edition (link) BibTeX
Amin Coja-Oghlan, Cristopher Moore, Vishal Sanwalani:
Counting Connected Graphs and Hypergraphs via the Probabilistic Method. 322-333
Electronic Edition (link) BibTeX
Yevgeniy Dodis, Ariel Elbaz, Roberto Oliveira, Ran Raz:
Improved Randomness Extraction from Two Independent Sources. 334-344
Electronic Edition (link) BibTeX
Abraham Flaxman, Alan M. Frieze:
The Diameter of Randomly Perturbed Digraphs and Some Applications.. 345-356
Electronic Edition (link) BibTeX
David Gamarnik, Tomasz Nowicki, Grzegorz Swirszcz:
Maximum Weight Independent Sets and Matchings in Sparse Random Graphs. Exact Results Using the Local Weak Convergence Method. 357-368
Electronic Edition (link) BibTeX
Sumit Ganguly:
Estimating Frequency Moments of Data Streams Using Random Linear Combinations. 369-380
Electronic Edition (link) BibTeX
Dan Gutfreund, Emanuele Viola:
Fooling Parity Tests with Parity Gates. 381-392
Electronic Edition (link) BibTeX
Shirley Halevy, Eyal Kushilevitz:
Distribution-Free Connectivity Testing. 393-404
Electronic Edition (link) BibTeX
Michael Langberg:
Testing the Independence Number of Hypergraphs. 405-416
Electronic Edition (link) BibTeX
Luca Trevisan:
A Note on Approximate Counting for k-DNF. 417-426
Electronic Edition (link) BibTeX