|
| |
Invited speakers
Papers accepted at APPROX+RANDOM 2007
Program
Currently showing program for 2006. Program for 2007 will be
posted at a later time.
| (download
file) |
|
Opening |
| 9:00 - 9:50 |
Invited talk
Nick Wormald
Analysis of algorithms on the cores of random
graphs
|
| 9:50-10:15 |
Chandra Chekuri and Martin Pal.
An O(log n) Approximation Ratio for the
Asymmetric Traveling Salesman Path Problem
|
| 10:15-10:40 |
Dana Ron and Oded Goldreich.
Approximating Average Parameters of Graphs
|
| 10:40 - 11:00 |
Coffee break |
| 11:00-12:40 |
RANDOM session |
|
Martin Marciniszyn, Jozef Skokan, Reto Spöhel and
Angelika Steger
Threshold Functions for
Asymmetric Ramsey Properties Involving Cliques
|
|
Sharon Marko and Dana Ron.
Distance Approximation in Bounded-Degree and
General Sparse Graphs
|
|
Thomas Strohmer and Roman Vershynin.
A randomized solver for linear systems with
exponential convergence
|
|
Uriel Feige, Elchanan Mossel and Dan Vilenchik.
Complete convergence of message
passing algorithms for some satisfiability problems
|
| 12:40 - 15:00 |
Lunch |
| 15:00-16:40 |
APPROX session |
|
T-H. Hubert Chan, Donglin Xia, Goran Konjevod and
Andrea Richa.
A Tight Lower Bound for
the Steiner Point Removal Problem on Trees
|
|
Christoph Ambühl, Thomas Erlebach, Matus Mihalak and
Marc Nunkesser.
Constant-factor
approximation for minimum-weight (connected) dominating sets in unit
disk graphs
|
|
MohammadTaghi Hajiaghayi, Guy Kortsarz and
MohammadReza Salavatipour.
Approximating Buy-at-Bulk and Shallow-light
$-Steiner trees
|
|
Anthony Man-Cho So, Jiawei Zhang and Yinyu
Ye.
Stochastic Combinatorial
Optimization with Controllable Risk Aversion Level
|
| 16:40-17:00 |
Coffee break |
| 17:00-18:40 |
RANDOM session |
|
Amit Deshpande and Santosh Vempala.
Adaptive Sampling and Fast Low-Rank Matrix
Approximation
|
|
Sanjeev Arora, Elad Hazan and Satyen Kale.
A Fast Random Sampling Algorithm for Sparsifying
Matrices
|
|
Petros Drineas, Michael Mahoney and S. (Muthu)
Muthukrishnan.
Subspace Sampling and
Relative-Error Matrix Approximation: Column-Based Methods
|
|
Rajeev Motwani, Rina Panigrahy and Ying Xu.
Fractional Matching via Balls-and-Bins
|
| 19:00 |
Reception at the restaurant
Notable of the UPC (just in front of the
conference room) |
| (download
file) |
| 9:00-10:40 |
APPROX session |
|
Alexander Grigoriev, Maxim Sviridenko and Marc
Uetz.
LP Rounding and an Almost
Harmonic Algorithm for Scheduling with Resource Dependent Processing
Times
|
|
Benjamin Birnbaum and Kenneth Goldman.
An Improved Analysis for a Greedy Remote-Clique
Algorithm using Factor-Revealing LPs
|
|
Michael Langberg, Yuval Rabani and Chaitanya
Swamy.
Approximation Algorithms for
Graph Homomorphism Problems
|
|
Jean Cardinal, Samuel Fiorini and Gwenaël
Joret.
Tight Results on Minimum Entropy
Set Cover
|
| 10:40-11:00 |
Coffee break |
| 11:00-12:40 |
RANDOM session |
|
Irit Dinur, Madhu Sudan and Avi Wigderson.
Robust local testability of tensor products of
LDPC
|
|
Yi-Kai Liu, Vadim Lyubashevsky and Daniele
Micciancio.
On Bounded Distance
Decoding for General Lattices
|
|
Elena Grigorescu, Swastik Kopparty and Madhu Sudan.
Local Decoding and Testing for
Homomorphisms
|
|
Yi-Kai Liu.
Consistency
of Local Density Matrices is QMA-complete
|
| 12:40-15:00 |
Lunch |
| 15:00-16:40 |
APPROX session |
|
Viswanath Nagarajan and R. Ravi.
Minimum vehicle routing with a common deadline
|
|
Inge Li Goertz.
Hardness
of Preemptive Finite Capacity Dial-a-Ride
|
|
Nikhil Bansal, Don Coppersmith and Baruch
Schieber.
Minimizing Setup and Beam-On
Times in Radiation Therapy
|
|
Zeev Nutov.
Approximating minimum power covers of
intersecting families and directed connectivity problems
|
| 16:40-17:00 |
Coffee break |
| 17:00-18:40 |
APPROX session |
|
Christoph Ambühl, Monaldo Mastrolilli and Ola
Svensson.
Approximating
Precedence-Constrained Single Machine Scheduling by Coloring
|
|
Leah Epstein, Magnus Halldorsson, Asaf Levin and
Hadas Shachnai.
Weighted Sum Coloring
in Batch Scheduling of Conflicting Jobs
|
|
Samir Khuller, Azarakhsh Malekian and Yoo-Ah
Kim.
Improved Algorithms for Data
Migration
|
|
Rajiv Gandhi and Julian Mestre.
Combinatorial Algorithms for Data Migration to
Minimize Average Completion Time
|
| 21:00 |
Social dinner
(see the Social
Events section for more details) |
| (download
file) |
| 9:00 - 9:50 |
Invited talk
Johan Håstad
On non trivial approximations of CSPs
|
| 9:50-10:15 |
Benny Applebaum, Yuval Ishai and Eyal Kushilevitz.
On Pseudorandom Generators with Linear
Stretch in NC0
|
|
Retsef Levi and Maxim Sviridenko.
Improved Approximation Algorithm for the
One-Warehouse Multi-Retailer Problem
|
| 10:40-11:00 |
Coffee break |
| 11:00-12:40 |
RANDOM session |
|
Martin Dyer, Leslie Goldberg and Mark
Jerrum.
Dobrushin conditions and
Systematic Scan
|
|
Murali Ganapathy.
Robust
Mixing Time
|
|
Nayantara Bhatnagar, Sam Greenberg and Dana
Randall.
The Effect of Boundary
Conditions on Mixing Rates of Markov Chains
|
|
Philipp Woelfel.
Maintaining External Memory Efficient Hash
Tables
|
| 12:40-15:00 |
Lunch |
| 15:00-16:40 |
APPROX session |
|
Shuchi Chawla and Tim Roughgarden.
Single-Source Stochastic Routing
|
|
Sashka Davis, Jeff Edmonds and Russell
Imagliazzo.
Online Algorithms To
Minimize Resource Reallocations and Network Communication
|
|
David Woodruff.
Better
Approximations for the Minimum Common Integer Partition Problem
|
|
Rene Sitters, Gil Shallom, Yair Bartal and Stefano
Leonardi.
On the Value of Preemption in
Scheduling
|
| 16:40-17:00 |
Coffee break |
| 17:00-18:40 |
RANDOM session |
|
Avner magen, Shlomo hoory and Toniann
Pitassi.
Monotone circuits for the
majority function
|
|
Alexander Healy.
Randomness-Efficient Sampling within
NC1
|
|
Dan Gutfreund.
Wort-case
vs. algorithmic average-case complexity in the polynomial-time
hierarchy
|
|
Oded Lachish, Ilan Newman and Asaf Shapira.
Space Complexity vs. Query Complexity
|
| End of the
conference |
|
|