default search action
12th RANDOM / 11th APPROX 2008: Boston, MA, USA
- Ashish Goel, Klaus Jansen, José D. P. Rolim, Ronitt Rubinfeld:
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
Contributed Talks of APPROX
- Micah Adler, Brent Heeringa:
Approximating Optimal Binary Decision Trees. 1-9 - Arash Asadpour, Uriel Feige, Amin Saberi:
Santa Claus Meets Hypergraph Matchings. 10-20 - Mihai Badoiu, Erik D. Demaine, MohammadTaghi Hajiaghayi, Anastasios Sidiropoulos, Morteza Zadimoghaddam:
Ordinal Embedding: Approximation Algorithms and Dimensionality Reduction. 21-34 - Jean Cardinal, Eythan Levy:
Connected Vertex Covers in Dense Graphs. 35-48 - Eden Chlamtac, Gyanit Singh:
Improved Approximation Guarantees through Higher Levels of SDP Hierarchies. 49-62 - Adrian Dumitrescu, Minghui Jiang:
Sweeping Points. 63-76 - Venkatesan Guruswami, Prasad Raghavendra:
Constraint Satisfaction over a Non-Boolean Domain: Approximation Algorithms and Unique-Games Hardness. 77-90 - 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 - David R. Karger
Efficient Algorithms for Fixed-Precision Instances of Bin Packing and Euclidean TSP. 104-117 - Guy Kortsarz, Michael Langberg, Zeev Nutov:
Approximating Maximum Subgraphs without Short Cycles. 118-131 - Lukasz Kowalik, Marcin Mucha
Deterministic 7/8-Approximation for the Metric Maximum TSP. 132-145 - Yuval Lando, Zeev Nutov:
Inapproximability of Survivable Networks. 146-152 - Monaldo Mastrolilli
Approximating Single Machine Scheduling with Scenarios. 153-164 - Richard Matthew McCutchen
Streaming Algorithms for k-Center Clustering with Outliers and with Anonymity. 165-178 - Shashi Mittal, Andreas S. Schulz:
A General Framework for Designing Approximation Schemes for Combinatorial Optimization Problems with Many Objectives Combined into One. 179-192 - Viswanath Nagarajan, R. Ravi:
The Directed Minimum Latency Problem. 193-206 - Thành Nguyen:
A Simple LP Relaxation for the Asymmetric Traveling Salesman Problem. 207-218 - Zeev Nutov:
Approximating Directed Weighted-Degree Constrained Networks. 219-232 - MohammadAli Safari, Mohammad R. Salavatipour:
A Constant Factor Approximation for Minimum lambda-Edge-Connected k-Subgraph with Metric Costs. 233-246 - Aravind Srinivasan
Budgeted Allocations in the Full-Information Setting. 247-253
Contributed Talks of RANDOM
- Jeff Abrahamson, Béla Csaba
Optimal Random Matchings on Trees and Applications. 254-265 - Noga Alon, Ido Ben-Eliezer, Michael Krivelevich:
Small Sample Spaces Cannot Fool Low Degree Polynomials. 266-275 - Vikraman Arvind, Partha Mukhopadhyay:
Derandomizing the Isolation Lemma and Lower Bounds for Circuit Size. 276-289 - Eli Ben-Sasson, Michael Viderman:
Tensor Products of Weakly Smooth Codes Are Robust. 290-302 - Nicla Bernasconi, Konstantinos Panagiotou, Angelika Steger:
On the Degree Sequences of Random Outerplanar and Series-Parallel Graphs. 303-316 - Eric Blais:
Improved Bounds for Testing Juntas. 317-330 - Andrej Bogdanov, Elchanan Mossel
The Complexity of Distinguishing Markov Random Fields. 331-342 - Guy Bresler, Elchanan Mossel
Reconstruction of Markov Random Fields from Samples: Some Observations and Algorithms. 343-356 - Kai-Min Chung, Salil P. Vadhan:
Tight Bounds for Hashing Block Sources. 357-370 - Matei David, Toniann Pitassi, Emanuele Viola:
Improved Separations between Nondeterministic and Randomized Multiparty Communication. 371-384 - Hang Dinh, Alexander Russell
Quantum and Randomized Lower Bounds for Local Search on Vertex-Transitive Graphs. 385-401 - Eldar Fischer, Oded Lachish
On the Query Complexity of Testing Orientations for Being Eulerian. 402-415 - Martin Fürer
Approximately Counting Embeddings into Random Graphs. 416-429 - Ariel Gabizon, Ronen Shaltiel:
Increasing the Output Length of Zero-Error Dispersers. 430-443 - Venkatesan Guruswami, James R. Lee, Avi Wigderson:
Euclidean Sections of with Sublinear Randomness and Error-Correction over the Reals. 444-454 - Dan Gutfreund, Guy N. Rothblum:
The Complexity of Local List Decoding. 455-468 - Dan Gutfreund, Salil P. Vadhan:
Limitations of Hardness vs. Randomness under Uniform Reductions. 469-482 - Jeffrey C. Jackson
Learning Random Monotone DNF. 483-497 - Tali Kaufman, Simon Litsyn, Ning Xie:
Breaking the epsilon-Soundness Bound of the Linearity Test over GF(2). 498-511 - Edo Liberty, Nir Ailon, Amit Singer
Dense Fast Random Projections and Lean Walsh Transforms. 512-522 - Avner Magen, Anastasios Zouzias:
Near Optimal Dimensionality Reductions That Preserve Volumes. 523-534 - Hariharan Narayanan
Sampling Hypersurfaces through Diffusion. 535-548 - Anup Rao:
A 2-Source Almost-Extractor for Linear Entropy. 549-556 - Anup Rao, David Zuckerman:
Extractors for Three Uneven-Length Sources. 557-570 - Gregory B. Sorkin
The Power of Choice in a Generalized Pólya Urn Model. 571-583 - David P. Woodruff:
Corruption and Recovery-Efficient Locally Decodable Codes. 584-595 - Raphael Yuster:
Quasi-randomness Is Determined by the Distribution of Copies of a Fixed Graph in Equicardinal Large Sets. 596-601
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2024-12-17 20:46 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: