12. RANDOM / 11. APPROX 2008:
Boston,
MA,
USA
Ashish Goel, Klaus Jansen, José D. P. Rolim, Ronitt Rubinfeld (Eds.):
Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques, 11th International Workshop, APPROX 2008, and 12th International Workshop, RANDOM 2008, Boston, MA, USA, August 25-27, 2008. Proceedings.
Lecture Notes in Computer Science 5171 Springer 2008, ISBN 978-3-540-85362-6 BibTeX
Contributed Talks of APPROX
- Micah Adler, Brent Heeringa:
Approximating Optimal Binary Decision Trees.
1-9
Electronic Edition (link) BibTeX
- Arash Asadpour, Uriel Feige, Amin Saberi:
Santa Claus Meets Hypergraph Matchings.
10-20
Electronic Edition (link) BibTeX
- Mihai Badoiu, Erik D. Demaine, MohammadTaghi Hajiaghayi, Anastasios Sidiropoulos, Morteza Zadimoghaddam:
Ordinal Embedding: Approximation Algorithms and Dimensionality Reduction.
21-34
Electronic Edition (link) BibTeX
- Jean Cardinal, Eythan Levy:
Connected Vertex Covers in Dense Graphs.
35-48
Electronic Edition (link) BibTeX
- Eden Chlamtac, Gyanit Singh:
Improved Approximation Guarantees through Higher Levels of SDP Hierarchies.
49-62
Electronic Edition (link) BibTeX
- Adrian Dumitrescu, Minghui Jiang:
Sweeping Points.
63-76
Electronic Edition (link) BibTeX
- Venkatesan Guruswami, Prasad Raghavendra:
Constraint Satisfaction over a Non-Boolean Domain: Approximation Algorithms and Unique-Games Hardness.
77-90
Electronic Edition (link) BibTeX
- Nir Halman, Chung-Lun Li, David Simchi-Levi:
Fully Polynomial Time Approximation Schemes for Time-Cost Tradeoff Problems in Series-Parallel Project Networks.
91-103
Electronic Edition (link) BibTeX
- David R. Karger, Jacob Scott:
Efficient Algorithms for Fixed-Precision Instances of Bin Packing and Euclidean TSP.
104-117
Electronic Edition (link) BibTeX
- Guy Kortsarz, Michael Langberg, Zeev Nutov:
Approximating Maximum Subgraphs without Short Cycles.
118-131
Electronic Edition (link) BibTeX
- Lukasz Kowalik, Marcin Mucha:
Deterministic 7/8-Approximation for the Metric Maximum TSP.
132-145
Electronic Edition (link) BibTeX
- Yuval Lando, Zeev Nutov:
Inapproximability of Survivable Networks.
146-152
Electronic Edition (link) BibTeX
- Monaldo Mastrolilli, Nikolaus Mutsanas, Ola Svensson:
Approximating Single Machine Scheduling with Scenarios.
153-164
Electronic Edition (link) BibTeX
- Richard Matthew McCutchen, Samir Khuller:
Streaming Algorithms for k-Center Clustering with Outliers and with Anonymity.
165-178
Electronic Edition (link) BibTeX
- Shashi Mittal, Andreas S. Schulz:
A General Framework for Designing Approximation Schemes for Combinatorial Optimization Problems with Many Objectives Combined into One.
179-192
Electronic Edition (link) BibTeX
- Viswanath Nagarajan, R. Ravi:
The Directed Minimum Latency Problem.
193-206
Electronic Edition (link) BibTeX
- Thành Nguyen:
A Simple LP Relaxation for the Asymmetric Traveling Salesman Problem.
207-218
Electronic Edition (link) BibTeX
- Zeev Nutov:
Approximating Directed Weighted-Degree Constrained Networks.
219-232
Electronic Edition (link) BibTeX
- MohammadAli Safari, Mohammad R. Salavatipour:
A Constant Factor Approximation for Minimum lambda-Edge-Connected k-Subgraph with Metric Costs.
233-246
Electronic Edition (link) BibTeX
- Aravind Srinivasan:
Budgeted Allocations in the Full-Information Setting.
247-253
Electronic Edition (link) BibTeX
Contributed Talks of RANDOM
- Jeff Abrahamson, Béla Csaba, Ali Shokoufandeh:
Optimal Random Matchings on Trees and Applications.
254-265
Electronic Edition (link) BibTeX
- Noga Alon, Ido Ben-Eliezer, Michael Krivelevich:
Small Sample Spaces Cannot Fool Low Degree Polynomials.
266-275
Electronic Edition (link) BibTeX
- Vikraman Arvind, Partha Mukhopadhyay:
Derandomizing the Isolation Lemma and Lower Bounds for Circuit Size.
276-289
Electronic Edition (link) BibTeX
- Eli Ben-Sasson, Michael Viderman:
Tensor Products of Weakly Smooth Codes Are Robust.
290-302
Electronic Edition (link) BibTeX
- Nicla Bernasconi, Konstantinos Panagiotou, Angelika Steger:
On the Degree Sequences of Random Outerplanar and Series-Parallel Graphs.
303-316
Electronic Edition (link) BibTeX
- Eric Blais:
Improved Bounds for Testing Juntas.
317-330
Electronic Edition (link) BibTeX
- Andrej Bogdanov, Elchanan Mossel, Salil P. Vadhan:
The Complexity of Distinguishing Markov Random Fields.
331-342
Electronic Edition (link) BibTeX
- Guy Bresler, Elchanan Mossel, Allan Sly:
Reconstruction of Markov Random Fields from Samples: Some Observations and Algorithms.
343-356
Electronic Edition (link) BibTeX
- Kai-Min Chung, Salil P. Vadhan:
Tight Bounds for Hashing Block Sources.
357-370
Electronic Edition (link) BibTeX
- Matei David, Toniann Pitassi, Emanuele Viola:
Improved Separations between Nondeterministic and Randomized Multiparty Communication.
371-384
Electronic Edition (link) BibTeX
- Hang Dinh, Alexander Russell:
Quantum and Randomized Lower Bounds for Local Search on Vertex-Transitive Graphs.
385-401
Electronic Edition (link) BibTeX
- Eldar Fischer, Oded Lachish, Ilan Newman, Arie Matsliah, Orly Yahalom:
On the Query Complexity of Testing Orientations for Being Eulerian.
402-415
Electronic Edition (link) BibTeX
- Martin Fürer, Shiva Prasad Kasiviswanathan:
Approximately Counting Embeddings into Random Graphs.
416-429
Electronic Edition (link) BibTeX
- Ariel Gabizon, Ronen Shaltiel:
Increasing the Output Length of Zero-Error Dispersers.
430-443
Electronic Edition (link) BibTeX
- Venkatesan Guruswami, James R. Lee, Avi Wigderson:
Euclidean Sections of with Sublinear Randomness and Error-Correction over the Reals.
444-454
Electronic Edition (link) BibTeX
- Dan Gutfreund, Guy N. Rothblum:
The Complexity of Local List Decoding.
455-468
Electronic Edition (link) BibTeX
- Dan Gutfreund, Salil P. Vadhan:
Limitations of Hardness vs. Randomness under Uniform Reductions.
469-482
Electronic Edition (link) BibTeX
- Jeffrey C. Jackson, Homin K. Lee, Rocco A. Servedio, Andrew Wan:
Learning Random Monotone DNF.
483-497
Electronic Edition (link) BibTeX
- Tali Kaufman, Simon Litsyn, Ning Xie:
Breaking the epsilon-Soundness Bound of the Linearity Test over GF(2).
498-511
Electronic Edition (link) BibTeX
- Edo Liberty, Nir Ailon, Amit Singer:
Dense Fast Random Projections and Lean Walsh Transforms.
512-522
Electronic Edition (link) BibTeX
- Avner Magen, Anastasios Zouzias:
Near Optimal Dimensionality Reductions That Preserve Volumes.
523-534
Electronic Edition (link) BibTeX
- Hariharan Narayanan, Partha Niyogi:
Sampling Hypersurfaces through Diffusion.
535-548
Electronic Edition (link) BibTeX
- Anup Rao:
A 2-Source Almost-Extractor for Linear Entropy.
549-556
Electronic Edition (link) BibTeX
- Anup Rao, David Zuckerman:
Extractors for Three Uneven-Length Sources.
557-570
Electronic Edition (link) BibTeX
- Gregory B. Sorkin:
The Power of Choice in a Generalized Pólya Urn Model.
571-583
Electronic Edition (link) BibTeX
- David P. Woodruff:
Corruption and Recovery-Efficient Locally Decodable Codes.
584-595
Electronic Edition (link) BibTeX
- Raphael Yuster:
Quasi-randomness Is Determined by the Distribution of Copies of a Fixed Graph in Equicardinal Large Sets.
596-601
Electronic Edition (link) BibTeX
Copyright © Sat May 16 22:58:17 2009
by Michael Ley (ley@uni-trier.de)
