ESA 2007

ESA Accepted Papers

WAOA 2007

PEGG 2007

,Tentative Schedule





Optional Tours

ESA 2007
Accepted Papers
15th Annual European Symposium on Algorithms
Eilat, Israel, October 8-10, 2007

ESA'07 Design and Analysis Track: Accepted papers

  1. Petr Hlineny and Sang-il Oum. Finding branch-decompositions and rank-decompositions
  2. Mario Szegedy and Mikkel Thorup. On the variance of subset sum estimation
  3. Noga Alon and Raphael Yuster. Fast algorithms for Maximum Subset Matching and All-Pairs Shortest Paths in graphs with a (not so) small vertex cover
  4. Yuval Lando and Zeev Nutov. On minimum power connectivity problems
  5. Mikkel Thorup. Compact Oracles for Approximate Distances around Obstacles in the Plane
  6. Wolfgang Bein, Lawrence Larmore and John Noga. Equitable Revisited
  7. Reuven Bar-Yehuda, Guy Flysher, Julian Mestre and Dror Rawitz. Approximation of Partial Capacitated Vertex Cover
  8. Israel Beniaminy, Zeev Nutov and Meir Ovadia. Approximating Interval Scheduling Problems with Bounded Profits
  9. Justo Puerto, Antonio M. Rodriguez-Chia and Arie Tamir. New results on Minimax Regret Single Facility Location Problems on Networks
  10. Amihood Amir, Tzvika Hartman, Oren Kapah, Avivit Levy and Ely Porat. On The Cost of Interchange Rearrangement in Strings
  11. Alexander Souza and Martin Hoefer. Tradeoffs and Average-Case Equilibria in Selfish Routing
  12. Frank Kammer. Determining the smallest k such that G is k-outerplanar
  13. Rina Panigrahy and Dilys Thomas. Finding Frequent Elements in non-bursty Streams
  14. Amos Israeli, Dror Rawitz and Oran Sharon. On the Complexity of Sequential Rectangle Placement in IEEE 802.16/WiMAX Systems
  15. Aristides Gionis and Tamir Tassa. k-Anonymization with Minimal Loss of Information
  16. Jakub Pawlewicz. Order Statistics in the Farey Sequences in Sublinear Time
  17. Amotz Bar-Noy and Joanna Klukowska. Finding Mobile Data: Efficiency vs. Location Inaccuracy
  18. Alexa Sharp. Distance Coloring
  19. Petra Berenbrink and Oliver Schulte. Evolutionary Equilibrium in Bayesian Routing Games: Specialization and Niche Formation
  20. Dimitris Fotakis. Stackelberg Strategies for Atomic Congestion Games
  21. Petra Berenbrink, Tom Friedetzky, Iman Hajirasouliha and Zengjian Hu. Convergence to Equilibria in Distributed, Selfish Reallocation Processes with Weighted Tasks
  22. Jihuan Ding, Tomas Ebenlendr, Jiri Sgall and Guochuan Zhang. Online scheduling of equal-length jobs on parallel machines
  23. Chien-Chung Huang. Two's Company, Three's a Crowd: Stable Family and Threesome Roommates Problems
  24. Shankar Kalyanaraman and Christopher Umans. Algorithms for Playing Games with Limited Randomness
  25. Niv Buchbinder, Kamal Jain and Joseph (Seffi) Naor. Online Primal-Dual Algorithms for Maximizing Ad-Auctions Revenue
  26. Nikhil Bansal, Niv Buchbinder, Anupam Gupta and Seffi Naor. An O(log k)-competitive Algorithm for Metric Bipartite Matching
  27. Otfried Cheong, Hazel Everett, Marc Glisse, Joachim Gudmundsson, Samuel Hornus, Sylvain Lazard, Mira Lee and Hyeon-Suk Na. Farthest-polygon Voronoi diagrams
  28. Sriram Pemmaraju and Imran Pirwani. Good Quality Virtual Realization of Unit Ball Graphs
  29. Julian Lorenz, Konstantinos Panagiotou and Angelika Steger. Optimal Algorithms for k-Search with Application in Option Pricing
  30. Alexander Grigoriev, Joyce van Loon, Maxim Sviridenko, Marc Uetz and Tjark Vredeveld. Bundle Pricing with Comparable Items
  31. Christoph Durr and Thang Nguyen Kim. Nash equilibria in Voronoi games on graphs
  32. Philippe Baptiste, Marek Chrobak and Christoph Durr. Polynomial Time Algorithms for Minimum Energy Scheduling
  33. Chi-Yuan Chan, Hung-I Yu, Wing-Kai Hon and Biing-Feng Wang. A Faster Query Algorithm for the Text Fingerprinting Problem
  34. Maren Martens, Fernanda Salazar and Martin Skutella. Convex Combinations of Single Source Unsplittable Flows
  35. Haim Kaplan, Natan Rubin and Micha Sharir. Linear Data Structures for Fast Ray-Shooting amidst Convex Polyhedra
  36. Anupam Gupta, MohammadTaghi Hajiaghayi, Viswanath Nagarajan and R Ravi. Dial a Ride from k-forest
  37. Alessandro Panconesi, Fabrizio Grandoni and Emilio De Santis. Fast Low Degree Connectivity of Ad-Hoc Networks via Percolation
  38. Miroslaw Kowaluk and Andrzej Lingas. Unique Lowest Common Ancestors in Dags are Almost as Easy as Matrix Multiplication
  39. Khaled Elbassioni, Rene Sitters and Yan Zhang. A Quasi-PTAS for Profit-Maximizing Pricing on Line Graphs
  40. Vineet Goyal, Anupam Gupta, Stefano Leonardi and R Ravi. Pricing Tree Access Networks with Connected Backbones
  41. Martin Mares and Milan Straka. Linear-Time Ranking of Permutations
  42. Alexander Golynski, Roberto Grossi, Ankur Gupta, Rajeev Raman and Srinivasa Rao Satti. On the Size of Succinct Indices
  43. Samir Khuller, Azarakhsh Malekian and Julian Mestre. To Fill or not to Fill: The Gas Station Problem
  44. Gianni Franceschini, S Muthukrishnan and Mihai Patrascu. Radix Sorting With No Extra Space
  45. Krzysztof Diks and Piotr Sankowski. Dynamic Plane Transitive Closure
  46. Michal Forisek, Branislav Katreniak, Jana Katreniakova, Rastislav Kralovic, Richard Kralovic, Vladimir Koutny, Dana Pardubska, Tomas Plachetka and Branislav Rovan. Online Bandwidth Allocation
  47. Koji Kobayashi and Kazuya Okamoto. Improved Upper Bounds on the Competitive Ratio for Online Realtime Scheduling
  48. Raphael Clifford, Klim Efremenko, Ely Porat and Amir Rothschild. k-mismatch with don't cares
  49. Cyril Gavoille and Arnaud Labourel. Shorter Implicit Representation for Planar Graphs and Bounded Treewidth Graphs
  50. Gerth Stolting Brodal, Rolf Fagerberg, Irene Finocchi, Fabrizio Grandoni, Giuseppe Italiano, Allan Gronlund Jorgensen, Gabriel Moruz, and Thomas M?lhave, Optimal Resilient Dynamic Dictionaries

ESA'07 Engineering and Applications Track: Accepted papers

  1. Cristina Bazgan, Hadrien Hugot and Daniel Vanderpooten. A practical efficient fptas for the 0-1 multi-objective knapsack problem
  2. Susanne Albers and Tobias Jacobs. An Experimental Study of New and Known Online Packet Buffering Algorithms
  3. Giorgio Ausiello, Camil Demetrescu, Paolo G. Franciosa, Giuseppe Italiano and Andrea Ribichini. Small Stretch Spanners in the Streaming Model: New Algorithms and Experiments
  4. Felix Konig, Marco Lobbecke, Rolf Mohring, Guido Schaefer and Ines Spenke. Solutions to Real-World Instances of PSPACE-Complete Stacking
  5. Laurent Dupont, Michael Hemmer, Sylvain Petitjean and Elmar Sch?mer. Complete, Exact and Efficient Implementation for Computing the Adjacency Graph of an Arrangment of Quadrics
  6. Markus Chimani, Maria Kandyba and Petra Mutzel. A New ILP Formulation for 2-Root-Connected Prize-Collecting Steiner Networks
  7. Luciana Buriol, Gereon Frahling, Stefano Leonardi and Christian Sohler. Estimating Clustering Indexes in Data Streams
  8. Julien Robert and Nicolas Schabanel. Non-Clairvoyant Batch Set Scheduling: Fairness is Fair enough
  9. Laurent Muller and Martin Zachariasen. Fast and Compact Oracles for Approximate Shortest Paths in Planar Graphs
  10. Arie Koster, Adrian Zymolka and Manuel Kutschka. Algorithms to separate {0,1/2}-Chvatal-Gomory cuts
  11. Stefan Eckhardt, Andreas Michael M?hling and Johannes Nowak. Fast Lowest Common Ancestor Computations in Dags
  12. Eric Berberich, Efi Fogel, Dan Halperin, Kurt Mehlhorn and Ron Wein. Sweeping and Maintaining Two-Dimensional Arrangements on Surfaces: A First Step
  13. Peter Hachenberger. Exact Minkowksi Sums of Polyhedra and Exact and Efficient Decomposition of Polyedra in Convex Pieces