Tuesday
Wednesday
***************** DESIGN AND ANALYSIS TRACK **********************
Less Hashing, Same Performance: Building a Better Bloom Filter Adam Kirsch and Michael Mitzenmacher
Estimating Entropy over Data Streams
Lakshminath Bhuvanagiri and Sumit Ganguly
Violator Spaces: Structure and Algorithms Bernd Gaertner, Jiri Matousek, Leo Ruest, Petr Skovron
Approximation results for preemptive stochastic online scheduling Nicole Megow and Tjark Vredeveld
Resource Allocation in Bounded Degree Trees Reuven Bar-Yehuda and Michael Beder and Yuval Cohen and Dror Rawitz
A Unified Approach to Approximating Partial Covering Problems Jochen Konemann and Ojas Parekh and Danny Segev
Path Hitting in Acyclic Graphs
Ojas Parekh and Danny Segev
Efficient Computation of Nash Equilibria for Very Sparse Win-Lose Bimatrix Games Bruno Codenotti and Mauro Leoncini and Giovanni Resta
Approximating almost all instances of Max-Cut within a ratio above the Hastad threshold A.C. Kaporis and L.M. Kirousis and E.C. Stavropoulos
Dynamic Programming and Fast Matrix Multiplication Frederic Dorn
Graph coloring with rejection
Leah Epstein and Asaf Levin and Gerhard J. Woeginger
Region-Restricted Clustering for Geographic Data Mining Joachim Gudmundsson and Marc van Kreveld and Giri Narasimham
Deciding Relaxed Two-Colorability - A Hardness Jump Robert Berke and Tibor Szabo
I/O-Efficient Undirected Shortest Paths with Unbounded Weights Ulrich Meyer and Norbert Zeh
An O(n^3 (log log n/ log n)^5/4 ) Time Algorithm for All Pairs Shortest Path Yijie Han
Cooperative TSP
Amitai Armon and Adi Avidor and Oded Schwartz
Negative Examples for Sequential Importance Sampling of Binary Contingency Tables Ivona Bezakova and Alistair Sinclair and Daniel Stefankovic and Eric Vigoda
Navigating Low-Dimensional and Hierarchical Population Networks Ravi Kumar and David Liben-Nowell and Andrew Tomkins
Approximate $k$-Steiner Forests via the Lagrangian Relaxation Technique with Internal Preprocessing Danny Segev and Gil Segev
Minimum Transversals in Posi-modular Systems Mariko Sakashita and Kazuhisa Makino and Hiroshi Nagamochi and Satoru Fujishige
A doubling dimension threshold theta(loglogn) for augmented graphs navigability Pierre Fraigniaud and Emmanuelle Lebhar and Zvi Lotker
Latency Constrained Aggregation in Sensor Networks Luca Becchetti and Peter Korteweg and Alberto Marchetti-Spaccamela and Martin Skutella and Leen Stougie and Andrea Vitaletti
Competitive Analysis of Flash-Memory Algorithms Avraham Ben-Aroya and Sivan Toledo
Kinetic Collision Detection for Convex Fat Objects Mohammad Ali Abam and Mark de Berg and Sheung-Hung Poon and Bettina Speckmann
Preemptive Online Scheduling: Optimal Algorithms for All Speeds Tomas Ebenlendr, Wojciech Jawor, Jiri Sgall
Spanners with Slack
T-H. Hubert Chan and Michael Dinitz and Anupam Gupta
Lower and Upper Bounds on FIFO Buffer Management in QoS Switches Matthias Englert and Matthias Westermann
On the