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