Logic List Mailing Archive
14th Annual European Symposium on Algorithms, Zuerich, Switzerland, September 2006
ESA 2006
14th Annual European Symposium on Algorithms
ETH Zurich, Zurich, Switzerland
September 11-13, 2006
http://algo06.inf.ethz.ch/esa
LIST OF ACCEPTED PAPERS
-----------------------
***************** 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 Complexity of the Multiplication Method for Monotone CNF/DNF
Dualization
Khaled Elbassioni
Distributed almost exact approximations for minor-closed families
Andrzej Czygrinow and Michal Hanckowiak
Purely Functional Worst Case Constant Time Catenable Sorted Lists
Gerth Brodal, Christos Makris, Kostas Tsichlas
Greedy in Approximation Algorithms
Julian Mestre
Balanced Pseudoflows: Algorithms and Applications
Robert Tarjan, Julie Ward, Bin Zhang, Yunhong Zhou and Jia Mao
Traversing the Machining Graph
Danny Z. Chen and Rudolf Fleischer and Jian Li and Haitao Wang
Enumerating Spanning and Connected Subsets in Graphs and Matroids
L. Khachiyan and E. Boros and K. Borys and K. Elbassioni and
V. Gurvich and K. Makino
Popular Matchings in the Capacitated House Allocation Problem
David F. Manlove and Colin T.S. Sng
Dynamic Algorithms for Maintaining Graph Spanners
Surender Baswana
Single machine precedence constrained scheduling is a vertex cover
problem
Christoph Ambuhl and Monaldo Mastrolilli
Frechet Distance for Curves, Revisited
Boris Aronov and Sariel Har-Peled and Christian Knauer and Yusu Wang
and Carola Wenk
On the Optimality of the Greedy Heuristic in Wavelet Synopses for
Range-Sum Queries
Yossi Matias and Daniel Urieli
Cheating by Men in the Gale-Shapley Stable Matching Algorithm
Chien-Chung Huang
Dynamic Connectivity for Axis-Parallel Rectangles
Peyman Afshani and Timothy M. Chan
Contention Resolution with Heterogeneous Job Sizes
Michael A. Bender and Jeremy T. Fineman and Seth Gilbert
Finding total unimodularity in optimization problems solved by linear
programs
Christoph Duerr and Mathilde Hurand
Near-Entropy Hotlink Assignments
Karim Douieb and Stefan Langerman
A New Approach to Stochastic Shortest Paths
Matthew Brand and Jonathan A. Kelner and Michael Mitzenmacher and
Evdokia Nikolova
Subspace Sampling and Relative-Error Matrix Approximation:
Column-Row-Based Methods
Petros Drineas and Michael W. Mahoney and S. Muthukrishnan
Compressed Indexes for Approximate String Matching
Ho-Leung Chan and Tak-Wah Lam and Wing-Kin Sung and Siu-Lung Tam and
Swee-Seong Wong
Spectral Clustering by Recursive Partitioning
Anirban Dasgupta and John Hopcroft and Ravi Kannan and Pradipta Mitra
Taxes for linear atomic congestion games
Ioannis Caragiannis and Christos Kaklamanis and
Panagiotis Kanellopoulos
Finite Termination of "Augmenting Path" Algorithms in the Presence of
Irrational Problem Data
Brian C. Dean and Michel X. Goemans and Nicole Immorlica
An LP-Designed Algorithm for Constraint Satisfaction
Alexander D. Scott and Gregory B. Sorkin
Necklaces, Convolutions, and X+Y
David Bremner and Timothy M. Chan and Erik D. Demaine and Jeff
Erickson and Ferran Hurtado and John Iacono and Stefan Langerman and
Ileana Streinu and Perouz Taslakian
************* ENGINEERING AND APPLICATIONS TRACK *****************
An MINLP solution method for a water network problem
Cristiana Bragalli and Claudia D'Ambrosio and Jon Lee and Andrea Lodi
and Paolo Toth
Exact and Efficient Construction of Planar Minkowski Sums using the
Convolution Method
Ron Wein
Multiline Addressing by Network Flow
Friedrich Eisenbrand and Andreas Karrenbauer and Martin Skutella and
Chihao Xu
Robust, Generic and Efficient Construction of Envelopes of Surfaces in
Three-Dimensional Space
Michal Meyerovitch
Parallel machine scheduling through column generation: minimax
objective functions
J.M. van den Akker and J.A. Hoogeveen and J.W. van Kempen
On exact algorithms for treewidth
Hans L. Bodlaender and Fedor V. Fomin and Arie M. C. A. Koster and
Dieter Kratsch and Dimitrios M. Thilikos
An Improved Construction for Counting Bloom Filters
Flavio Bonomi and Michael Mitzenmacher and Rina Panigrahy and
Sushil Singh and George Varghese
How Branch Mispredictions Affect Quicksort
Kanela Kaligosi and Peter Sanders
Reporting Flock Patterns
Marc Benkert and Joachim Gudmundsson and Florian Huebner and
Thomas Wolle
Engineering Highway Hierarchies
Peter Sanders and Dominik Schultes
Univariate polynomial real root isolation: Continued Fractions
revisited
Iaonnis Z. Emiris and Elias P. Tsigaridas
Algorithmic Aspects of Proportional Symbol Maps
Sergio Cabello and Herman Haverkort and Marc van Kreveld and
Bettina Speckmann
Kinetic Algorithms via Self-Adjusting Computation
Umut A. Acar and Guy E. Blelloch and Kanat Tangwongsan and
Jorge L. Vittes
Out-of-Order Event Processing in Kinetic Data Structures
Mohammad Ali Abam and Pankaj K. Agarwal and Mark de Berg and Hai Yu
Skewed Binary Search Trees
Gerth S. Brodal and Gabriel Moruz
The Price of Resiliency: A Case Study on Sorting with Memory Faults
Umberto Ferraro Petrillo and Irene Finocchi and Giuseppe F. Italiano
Does Path Cleaning Help in Dynamic All-Pairs Shortest Paths?
Camil Demetrescu, Pompeo Faruolo, Giuseppe F. Italiano, Mikkel Thorup
The Engineering of a Compression Boosting Library: Theory vs Practice
in BWT compression
P. Ferragina and R. Giancarlo and G. Manzini