default search action
9th RANDOM / 8th APPROX 2005: Berkeley, CA, USA
- Chandra Chekuri, Klaus Jansen, José D. P. Rolim, Luca Trevisan:
Approximation, Randomization and Combinatorial Optimization, Algorithms and Techniques, 8th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2005 and 9th InternationalWorkshop on Randomization and Computation, RANDOM 2005, Berkeley, CA, USA, August 22-24, 2005, Proceedings. Lecture Notes in Computer Science 3624, Springer 2005, ISBN 3-540-28239-4
Contributed Talks of APPROX
- Stanislav Angelov, Sanjeev Khanna, Keshav Kunal:
The Network as a Storage Device: Dynamic Routing with Bounded Buffers. 1-13 - Adi Avidor, Uri Zwick:
Rounding Two and Three Dimensional Solutions of the SDP Relaxation of MAX CUT. 14-25 - Kamalika Chaudhuri, Satish Rao, Samantha J. Riesenfeld
, Kunal Talwar:
What Would Edmonds Do? Augmenting Paths and Witnesses for Degree-Bounded MSTs. 26-39 - Victor Chepoi, Karim Nouioua, Yann Vaxès:
A Rounding Algorithm for Approximating Minimum Manhattan Networks. 40-51 - Joseph Cheriyan, Mohammad R. Salavatipour:
Packing Element-Disjoint Steiner Trees. 52-61 - Uriel Feige, Kunal Talwar:
Approximating the Bandwidth of Caterpillars. 62-73 - Anupam Gupta, Amit Kumar:
Where's the Winner? Max-Finding and Sorting with Metric Costs. 74-85 - Anupam Gupta, Martin Pál, R. Ravi, Amitabh Sinha:
What About Wednesday? Approximation Algorithms for Multistage Stochastic Optimization. 86-98 - Venkatesan Guruswami, Luca Trevisan:
The Complexity of Making Unique Choices: Approximating 1-in- k SAT. 99-110 - Alexander Hall, Christos H. Papadimitriou:
Approximating the Distortion. 111-122 - Boulos Harb, Sampath Kannan, Andrew McGregor:
Approximating the Best-Fit Tree Under Lp Norms. 123-133 - Gustav Hast:
Beating a Random Assignment. 134-145 - V. S. Anil Kumar, Madhav V. Marathe, Srinivasan Parthasarathy, Aravind Srinivasan:
Scheduling on Unrelated Machines Under Tree-Like Precedence Constraints. 146-157 - Jens Maßberg, Jens Vygen:
Approximation Algorithms for Network Design and Facility Location with Service Capacities. 158-169 - Andrew McGregor:
Finding Graph Matchings in Data Streams. 170-181 - Julián Mestre:
A Primal-Dual Approximation Algorithm for Partial Vertex Cover: Making Educated Guesses. 182-191 - Shlomo Moran, Sagi Snir:
Efficient Approximation of Convex Recolorings. 192-208 - Viswanath Nagarajan, R. Ravi:
Approximation Algorithms for Requirement Cut on Graphs. 209-220 - Jan Remy, Angelika Steger:
Approximation Schemes for Node-Weighted Geometric Steiner Tree Problems. 221-232 - Iannis Tourlakis:
Towards Optimal Integrality Gaps for Hypergraph Vertex Cover in the Lovász-Schrijver Hierarchy. 233-244
Contributed Talks of RANDOM
- Sourav Chakraborty, Jaikumar Radhakrishnan, Nandakumar Raghunathan:
Bounds for Error Reduction with Few Quantum Queries. 245-256 - Moses Charikar
Sampling Bounds for Stochastic Optimization. 257-269 - Zeev Dvir, Amir Shpilka
An Improved Analysis of Mergers. 270-281 - Uriel Feige, Eran Ofek:
Finding a Maximum Independent Set in a Sparse Random Graph. 282-293 - Ronen Gradwohl, Guy Kindler, Omer Reingold, Amnon Ta-Shma
On the Error Parameter of Dispersers. 294-305 - Venkatesan Guruswami, Atri Rudra:
Tolerant Locally Testable Codes. 306-317 - Venkatesan Guruswami, Salil P. Vadhan:
A Lower Bound on List Size for List Decoding. 318-329 - Shirley Halevy, Eyal Kushilevitz:
A Lower Bound for Distribution-Free Monotonicity Testing. 330-341 - Jeffrey C. Jackson, Rocco A. Servedio:
On Learning Random DNF Formulas Under the Uniform Distribution. 342-353 - Eyal Kaplan, Moni Naor, Omer Reingold:
Derandomized Constructions of k-Wise (Almost) Independent Permutations. 354-365 - Oded Lachish
Testing Periodicity. 366-377 - Vadim Lyubashevsky:
The Parity Problem in the Presence of Noise, Decoding Random Linear Codes, and the Subset Sum Problem. 378-389 - Martin Marciniszyn, Reto Spöhel, Angelika Steger:
The Online Clique Avoidance Game on Random Graphs. 390-401 - Rémi Monasson:
A Generating Function Method for the Average-Case Analysis of DPLL. 402-413 - Cristopher Moore
A Continuous-Discontinuous Second-Order Transition in the Satisfiability of Random Horn-SAT Formulas. 414-425 - Dana Randall, Peter Winkler:
Mixing Points on a Circle. 426-435 - Eyal Rozenman, Salil P. Vadhan:
Derandomized Squaring of Graphs. 436-447 - Dekel Tsur:
Tight Bounds for String Reconstruction Using Substring Queries. 448-459 - Christopher Umans:
Reconstructive Dispersers and Hitting Set Generators. 460-471 - Paul Valiant:
The Tensor Product of Two Codes Is Not Necessarily Robustly Testable. 472-481 - Raphael Yuster:
Fractional Decompositions of Dense Hypergraphs. 482-493
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-11-15 19:45 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: