default search action
13th RANDOM / 12th APPROX 2009: Berkeley, CA, USA
- Irit Dinur, Klaus Jansen, Joseph Naor, José D. P. Rolim:
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 12th International Workshop, APPROX 2009, and 13th International Workshop, RANDOM 2009, Berkeley, CA, USA, August 21-23, 2009. Proceedings. Lecture Notes in Computer Science 5687, Springer 2009, ISBN 978-3-642-03684-2
Contributed Talks of APPROX
- Ashkan Aazami, Joseph Cheriyan, Krishnam Raju Jampani:
Approximation Algorithms and Hardness Results for Packing Element-Disjoint Steiner Trees in Planar Graphs. 1-14 - Ankit Aggarwal, Amit Deshpande, Ravi Kannan:
Adaptive Sampling for k-Means Clustering. 15-28 - Douglas E. Carroll, Adam Meyerson, Brian Tagiku:
Approximations for Aligned Coloring and Spillage Minimization in Interval and Chordal Graphs. 29-41 - Chandra Chekuri, Alina Ene, Nitish Korula:
Unsplittable Flow in Paths and Trees and Column-Restricted Packing Integer Programs. 42-55 - Chandra Chekuri, Iftah Gamzu:
Truthful Mechanisms via Greedy Iterative Packing. 56-69 - Julia Chuzhoy, Paolo Codenotti:
Resource Minimization Job Scheduling. 70-83 - Julia Chuzhoy, Paolo Codenotti:
Erratum: Resource Minimization Job Scheduling. - José R. Correa, Martin Skutella, José Verschae:
The Power of Preemption on Unrelated Machines and Applications to Scheduling Orders. 84-97 - Friedrich Eisenbrand, Thomas Rothvoß:
New Hardness Results for Diophantine Approximation. 98-110 - Uriel Feige, Nicole Immorlica, Vahab S. Mirrokni, Hamid Nazerzadeh:
PASS Approximation. 111-124 - Konstantinos Georgiou, Avner Magen, Madhur Tulsiani:
Optimal Sherali-Adams Gaps from Pairwise Independence. 125-139 - Matt Gibson, Gaurav Kanade, Erik Krohn, Kasturi R. Varadarajan:
An Approximation Scheme for Terrain Guarding. 140-148 - Anupam Gupta, Ravishankar Krishnaswamy, Amit Kumar
, Danny Segev:
Scheduling with Outliers. 149-162 - Venkatesan Guruswami, Ali Kemal Sinop:
Improved Inapproximability Results for Maximum k-Colorable Subgraph. 163-176 - Rolf Harren, Rob van Stee:
Improved Absolute Approximation Ratios for Two-Dimensional Packing Problems. 177-189 - Alexander Jaffe, James R. Lee, Mohammad Moharrami:
On the Optimality of Gluing over Scales. 190-201 - Rohit Khandekar, Tracy Kimbrel, Konstantin Makarychev, Maxim Sviridenko:
On Hardness of Pricing Items for Single-Minded Bidders. 202-216 - Ronald Koch, Britta Peis, Martin Skutella, Andreas Wiese:
Real-Time Message Routing and Scheduling. 217-230 - Guy Kortsarz, Zeev Nutov:
Approximating Some Network Design Problems with Node Costs. 231-243 - Jon Lee
Submodular Maximization over Multiple Matroids via Generalized Exchange Properties. 244-257 - Avner Magen, Mohammad Moharrami:
Robust Algorithms for on Minor-Free Graphs Based on the Sherali-Adams Hierarchy. 258-271 - Adam Meyerson, Brian Tagiku:
Minimizing Average Shortest Path Distances via Shortcut Edge Addition. 272-285 - Zeev Nutov:
Approximating Node-Connectivity Augmentation Problems. 286-297 - Katarzyna E. Paluch
A 7/9 - Approximation Algorithm for the Maximum Traveling Salesman Problem. 298-311 - Saurav Pandit, Sriram V. Pemmaraju, Kasturi R. Varadarajan:
Approximation Algorithms for Domatic Partitions of Unit Disk Graphs. 312-325 - Thomas Rothvoß, Laura Sanità:
On the Complexity of the Asymmetric VPN Problem. 326-338
Contributed Talks of RANDOM
- Noga Alon, Rina Panigrahy, Sergey Yekhanin:
Deterministic Approximation Algorithms for the Nearest Codeword Problem. 339-351 - Boaz Barak, Anup Rao, Ran Raz, Ricky Rosen, Ronen Shaltiel:
Strong Parallel Repetition Theorem for Free Projection Games. 352-365 - Ido Ben-Eliezer, Rani Hod
Random Low Degree Polynomials are Hard to Approximate. 366-377 - Eli Ben-Sasson, Michael Viderman:
Composition of Semi-LTCs by Two-Wise Tensor Products. 378-391 - Andrej Bogdanov, Youming Qiao
On the Security of Goldreich's One-Way Function. 392-405 - S. Charles Brubaker, Santosh S. Vempala:
Random Tensors and Planted Cliques. 406-419 - Karthekeyan Chandrasekaran, Amit Deshpande, Santosh S. Vempala:
Sampling s-Concave Functions: The Limit of Convexity Based Isoperimetry. 420-433 - Prasad Chebolu, Alan M. Frieze, Páll Melsted
Average-Case Analyses of Vickrey Costs. 434-447 - Victor Chen:
A Hypergraph Dictatorship Test with Perfect Completeness. 448-461 - Anindya De, Luca Trevisan
Extractors Using Hardness Amplification. 462-475 - Klim Efremenko
How Well Do Random Walks Parallelize?. 476-489 - Alan M. Frieze, Páll Melsted
An Analysis of Random-Walk Cuckoo Hashing. 490-503 - Oded Goldreich
Hierarchy Theorems for Property Testing. 504-519 - Oded Goldreich
Algorithmic Aspects of Property Testing in the Dense Graphs Model. 520-533 - Elena Grigorescu, Tali Kaufman, Madhu Sudan:
Succinct Representation of Codes with Applications to Testing. 534-547 - Aram W. Harrow
Efficient Quantum Tensor Product Expanders and k-Designs. 548-561 - T. S. Jayram:
Hellinger Strikes Back: A Note on the Multi-party Information Complexity of AND. 562-573 - Jeff Kinne
Pseudorandom Generators and Typically-Correct Derandomization. 574-587 - Adam R. Klivans, Philip M. Long, Alex K. Tang:
Baum's Algorithm Learns Intersections of Halfspaces with Respect to Log-Concave Distributions. 588-600 - Swastik Kopparty, Shubhangi Saraf:
Tolerant Linearity Testing and Locally Testable Codes. 601-614 - Shachar Lovett
Pseudorandom Bit Generators That Fool Modular Sums. 615-630 - Brendan Lucier, Michael Molloy, Yuval Peres:
The Glauber Dynamics for Colourings of Bounded Degree Trees. 631-645 - Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld, Rocco A. Servedio:
Testing ±1-weight halfspace. 646-657 - Raghu Meka, David Zuckerman:
Small-Bias Spaces for Group Products. 658-672 - Lorenz Minder, Dan Vilenchik:
Small Clique Detection and Approximate Nash Equilibria. 673-685 - Dana Ron
Testing Computability by Width Two OBDDs. 686-699 - Amir Shpilka
Improved Polynomial Identity Testing for Read-Once Formulas. 700-713 - Terence Tao, Van H. Vu:
Smooth Analysis of the Condition Number and the Least Singular Value. 714-737
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-23 19:17 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: