default search action
10th RANDOM / 9th APPROX 2006: Barcelona, Spain
- Josep Díaz, Klaus Jansen, José D. P. Rolim, Uri Zwick:
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2006 and 10th International Workshop on Randomization and Computation, RANDOM 2006, Barcelona, Spain, August 28-30 2006, Proceedings. Lecture Notes in Computer Science 4110, Springer 2006, ISBN 3-540-38044-2
Invited Talks
- Johan Håstad:
On Nontrivial Approximation of CSPs. 1 - Nicholas C. Wormald:
Analysis of Algorithms on the Cores of Random Graphs. 2
Contributed Talks of APPROX
- Christoph Ambühl, Thomas Erlebach, Matús Mihalák, Marc Nunkesser:
Constant-Factor Approximation for Minimum-Weight (Connected) Dominating Sets in Unit Disk Graphs. 3-14 - Christoph Ambühl, Monaldo Mastrolilli, Ola Svensson:
Approximating Precedence-Constrained Single Machine Scheduling by Coloring. 15-26 - Nikhil Bansal, Don Coppersmith, Baruch Schieber:
Minimizing Setup and Beam-On Times in Radiation Therapy. 27-38 - Yair Bartal, Stefano Leonardi, Gil Shallom, René Sitters:
On the Value of Preemption in Scheduling. 39-48 - Benjamin E. Birnbaum, Kenneth J. Goldman:
An Improved Analysis for a Greedy Remote-Clique Algorithm Using Factor-Revealing LPs. 49-60 - Jean Cardinal, Samuel Fiorini, Gwenaël Joret:
Tight Results on Minimum Entropy Set Cover. 61-69 - T.-H. Hubert Chan, Donglin Xia, Goran Konjevod
, Andréa W. Richa:
A Tight Lower Bound for the Steiner Point Removal Problem on Trees. 70-81 - Shuchi Chawla, Tim Roughgarden:
Single-Source Stochastic Routing. 82-94 - Chandra Chekuri, Martin Pál:
An O(logn) Approximation Ratio for the Asymmetric Traveling Salesman Path Problem. 95-103 - Sashka Davis, Jeff Edmonds, Russell Impagliazzo
Online Algorithms to Minimize Resource Reallocations and Network Communication. 104-115 - Leah Epstein, Magnús M. Halldórsson, Asaf Levin
Weighted Sum Coloring in Batch Scheduling of Conflicting Jobs. 116-127 - Rajiv Gandhi, Julián Mestre:
Combinatorial Algorithms for Data Migration to Minimize Average Completion Time. 128-139 - Alexander Grigoriev
LP Rounding and an Almost Harmonic Algorithm for Scheduling with Resource Dependent Processing Times. 140-151 - Mohammad Taghi Hajiaghayi, Guy Kortsarz, Mohammad R. Salavatipour:
Approximating Buy-at-Bulk and Shallow-Light k-Steiner Trees. 152-163 - Samir Khuller, Yoo Ah Kim, Azarakhsh Malekian:
Improved Algorithms for Data Migration. 164-175 - Michael Langberg, Yuval Rabani
Approximation Algorithms for Graph Homomorphism Problems. 176-187 - Retsef Levi, Maxim Sviridenko:
Improved Approximation Algorithm for the One-Warehouse Multi-Retailer Problem. 188-199 - Inge Li Gørtz:
Hardness of Preemptive Finite Capacity Dial-a-Ride. 200-211 - Viswanath Nagarajan, R. Ravi:
Minimum Vehicle Routing with a Common Deadline. 212-223 - Anthony Man-Cho So
Stochastic Combinatorial Optimization with Controllable Risk Aversion Level. 224-235 - Zeev Nutov:
Approximating Minimum Power Covers of Intersecting Families and Directed Connectivity Problems. 236-247 - David P. Woodruff:
Better Approximations for the Minimum Common Integer Partition Problem. 248-259
Contributed Talks of RANDOM
- Benny Applebaum, Yuval Ishai, Eyal Kushilevitz:
On Pseudorandom Generators with Linear Stretch in NC0. 260-271 - Sanjeev Arora, Elad Hazan, Satyen Kale:
A Fast Random Sampling Algorithm for Sparsifying Matrices. 272-279 - Nayantara Bhatnagar, Sam Greenberg, Dana Randall:
The Effect of Boundary Conditions on Mixing Rates of Markov Chains. 280-291 - Amit Deshpande, Santosh S. Vempala:
Adaptive Sampling and Fast Low-Rank Matrix Approximation. 292-303 - Irit Dinur, Madhu Sudan, Avi Wigderson:
Robust Local Testability of Tensor Products of LDPC Codes. 304-315 - Petros Drineas, Michael W. Mahoney, S. Muthukrishnan:
Subspace Sampling and Relative-Error Matrix Approximation: Column-Based Methods. 316-326 - Martin E. Dyer
Dobrushin Conditions and Systematic Scan. 327-338 - Uriel Feige, Elchanan Mossel, Dan Vilenchik:
Complete Convergence of Message Passing Algorithms for Some Satisfiability Problems. 339-350 - Murali K. Ganapathy:
Robust Mixing. 351-362 - Oded Goldreich, Dana Ron:
Approximating Average Parameters of Graphs. 363-374 - Elena Grigorescu, Swastik Kopparty, Madhu Sudan:
Local Decoding and Testing for Homomorphisms. 375-385 - Dan Gutfreund:
Worst-Case Vs. Algorithmic Average-Case Complexity in the Polynomial-Time Hierarchy. 386-397 - Alexander Healy:
Randomness-Efficient Sampling Within NC1. 398-409 - Shlomo Hoory, Avner Magen, Toniann Pitassi:
Monotone Circuits for the Majority Function. 410-425 - Oded Lachish
Space Complexity vs. Query Complexity. 426-437 - Yi-Kai Liu:
Consistency of Local Density Matrices Is QMA-Complete. 438-449 - Yi-Kai Liu, Vadim Lyubashevsky, Daniele Micciancio
On Bounded Distance Decoding for General Lattices. 450-461 - Martin Marciniszyn, Jozef Skokan
Threshold Functions for Asymmetric Ramsey Properties Involving Cliques. 462-474 - Sharon Marko, Dana Ron:
Distance Approximation in Bounded-Degree and General Sparse Graphs. 475-486 - Rajeev Motwani, Rina Panigrahy, Ying Xu:
Fractional Matching Via Balls-and-Bins. 487-498 - Thomas Strohmer, Roman Vershynin:
A Randomized Solver for Linear Systems with Exponential Convergence. 499-507 - Philipp Woelfel:
Maintaining External Memory Efficient Hash Tables. 508-519
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-15 01:14 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: