Accepted Papers

 
  • Bela Bollobas, David Pritchard, Thomas Rothvoss and Alex Scott. Cover-Decomposition and Polychromatic Numbers
  • Akiyoshi Shioura. Polynomial-Time Approximation Schemes for Maximizing Gross Substitutes Utility under Budget Constraints
  • Oren Salzman, Michael Hemmer, Barak Raveh and Dan Halperin. Motion Planning Via Manifold Samples
  • Dimitrios Thilikos. Fast sub-exponential Algorithms and Compactness in Planar Graphs
  • Gwenaël Joret, Christophe Paul, Ignasi Sau, Saket Saurabh and Stéphan Thomassé. Hitting and Harvesting Pumpkins
  • Ran Roth, Yossi Azar and Iftah Gamzu. Submodular Max-SAT
  • Monika Henzinger and Angelina Vidali. Multi-parameter mechanism design under budget and matroid constraints.
  • Chien-Chung Huang and Telikepalli Kavitha. Near-popular matchings in the Roommates problem
  • Yusuke Kobayashi and Yuichi Yoshida. Algorithms for Finding a Maximum Non-k-linked Graph
  • Hristo Djidjev and Christian Sommer. Approximate Distance Queries for Weighted Polyhedral Surfaces
  • Paweł Pszona and Michael T. Goodrich. External-Memory Network Analysis Algorithms for Naturally Sparse Graphs
  • Barna Saha, Saeed Alaei, Vahid Liaghat, Mohammad Taghi Hajiaghayi and Dan Pei. AdCell: Ad Allocation in Cellular Networks
  • Moran Feldman, Seffi Naor and Roy Schwartz. Improved Approximations for $k$-Coverable Set Systems
  • Paul Goldberg, Rahul Savani, Troels Sørensen and Carmine Ventre. On the Approximation Performance of Fictitious Play in Finite Games
  • Peter Sanders and Christian Schulz. Engineering Multilevel Graph Partitioning Algorithms
  • José Verschae and Andreas Wiese. On the Configuration-LP for Scheduling on Unrelated Machines
  • Djamal Belazzougui and Gonzalo Navarro. Alphabet-Independent Compressed Text Indexing
  • Asaf Frieder and Liam Roditty. An experimental study on approximating $K$ shortest simple paths
  • Ely Porat and Liam Roditty. Preprocess, Set, \textit{Query!}
  • Leah Epstein and Asaf Levin. Robust algorithms for preemptive scheduling
  • Pawel Gawrychowski. Pattern matching in Lempel-Ziv compressed strings: fast, simple, and deterministic
  • Hakan Yıldız, Luca Foschini, John Hershberger and Subhash Suri. The Union of Probabilistic Boxes: Maintaining the Volume
  • Paolo Ferragina, Jouni Sirén and Rossano Venturini. Distribution-aware compressed full-text indexes
  • Martin Dietzfelbinger, Michael Mitzenmacher and Michael Rink. Cuckoo Hashing with Pages
  • Danny Z. Chen and Haitao Wang. A Nearly Optimal Algorithm for Finding L_1 Shortest Paths among Polygonal Obstacles in the Plane
  • Fedor Fomin, Ioan Todinca and Yngve Villanger. Exact algorithm for the maximum induced planar subgraph problem
  • Tobias Brunsch, Heiko Röglin, Cyriel Rutten and Tjark Vredeveld. Smoothed Performance Guarantees for Local Search
  • Pascal Schweitzer. Isomorphism of (mis)labeled graphs
  • Ning Chen, Xiaotie Deng and Jie Zhang. How Profitable are Strategic Behaviors in a Market?
  • Chih-Hung Liu, Evanthia Papadopoulou and Der-Tsai Lee. An Output-Sensitive Approach for the L_1/L_infinity k Nearest Neighbor Voronoi Diagram
  • Saurabh Ray, Nabil Mustafa and Mudassir Shabbir. Ray-Shooting Depth:  Computing Statistical Data Depth of Point Sets in the Plane
  • Petr Hlineny and Ondrej Moris. Scope-Based Route Planning
  • Madhusudan Manjunath, Kurt Mehlhorn, Konstantinos Panagiotou and He Sun. Approximate Counting of Cycles in Streams
  • George Christodoulou, Kurt Mehlhorn and Evangelia Pyrga. Improving the Price of Anarchy for Selfish Routing via Coordination Mechanisms
  • Łukasz Jeż. One to Rule Them All: a General Randomized Algorithm for Buffer Management with Bounded Delay
  • Paul Bouman, Marjan Van Den Akker and Han Hoogeveen. Recoverable robustness by column generation
  • Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk and Jakub Wojtaszczyk. Scheduling partially ordered jobs faster than 2^n
  • Andrew Goldberg, Sagi Hed, Haim Kaplan, Robert Tarjan and Renato Werneck. Maximum Flows by Incremental Breadth-First Search
  • Thorsten Ederer, Ulf Lorenz, Alexander Martin and Jan Wolf. Quantified Linear Programs: A Computational Study
  • Aparna Das, Emden R. Gansner, Michael Kaufmann, Stephen Kobourov, Joachim Spoerhase and Alexander Wolff. Approximating Minimum Manhattan Networks in Higher Dimensions
  • Josep Diaz, Alberto Marchetti-Spaccamela, Dieter Mitsche, Paolo Santi and Julinda Stefa. Social-Aware Forwarding Improves Routing Performance in Pocket Switched Networks
  • Annabell Berger, Christian Blaar, Andreas Gebhardt, Matthias Müller-Hannemann and Mathias Schnee. Passenger Flow Oriented Train Disposition
  • Sanjoy Baruah, Vincenzo Bonifaci, Gianlorenzo D'Angelo, Alberto Marchetti-Spaccamela, Suzanne Van Der Ster and Leen Stougie. Mixed-Criticality Scheduling of Sporadic Task Systems
  • Basile Couëtoux. A 3/2 approximation for a constrained forest problem
  • Nir Ailon, Noa Avigdor-Elgrabli, Edo Liberty and Anke Van Zuylen. Improved Approximation Algorithms for Bipartite Correlation Clustering
  • Andreas Emil Feldmann and Peter Widmayer. An O(n^4 ) Time Algorithm to Compute the Bisection Width of Grid Graphs
  • Jurek Czyzowicz, Leszek Gasieniec, Adrian Kosowski and Evangelos Kranakis. Boundary Patrolling by Mobile Agents with Distinct Maximal Speeds
  • Marek Chrobak, Lukasz Jez and Jiří Sgall. Better Bounds for Incremental Frequency Allocation in Bipartite Graphs
  • Marek Chrobak, Jiri Sgall and Gerhard J. Woeginger. Two-bounded space bin packing revisited
  • Guy Even and Shakhar Smorodinsky. Hitting Sets Online and Vertex Ranking
  • Claudio Telha Cornejo and Andreas S. Schulz. Approximation Algorithms and Hardness Results for the Joint Replenishment Problem with Constant Demands
  • Venkatesh Raman, Ramanujan M S and Saket Saurabh. Paths, Flowers and Vertex Cover
  • Rui Ferreira, Roberto Grossi and Romeo Rizzi. Output-Sensitive Listing of Bounded-Size Trees in Undirected Graphs
  • Rolf Klein, Rainer Penninger, Christian Sohler and David Woodruff. Tolerant Algorithms
  • Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Anna Lubiw and Andrew Winslow. Algorithms for Solving Rubik’s Cubes
  • Matt Gibson, Gaurav Kanade and Kasturi Varadarajan. On Isolating Points using Disks
  • Shayan Oveis Gharan and Jan Vondrak. On Variants of the Matroid Secretary Problem
  • Yossi Azar, Ori Gurel-Gurevich, Eyal Lubetzky and Thomas Moscibroda. Optimal Discovery Strategies in White Space Networks
  • Justin Ward. Non-Oblivious Local Search, Matroid k-Parity, and k-Exchange Systems
  • Kaspar Schüpbach and Rico Zenklusen. Approximation Algorithms for Conflict-Free Vehicle Routing
  • Nikhil Bansal and Joel Spencer. Deterministic Discrepancy Minimization
  • Koki Hamada, Kazuo Iwama and Shuichi Miyazaki. The Hospitals/Residents Problem with Quota Lower Bounds
  • Loukas Georgiadis. Approximating the Smallest 2-Vertex Connected Spanning Subgraph of a Directed Graph
  • Jakub Łącki and Piotr Sankowski. Min-cuts and Shortest Cycles in Planar Graphs in $O(n \log \log n)$ Time
  • Anil Maheshwari, Jörg-Rüdiger Sack, Kaveh Shahbaz and Hamid Zarrabi-Zadeh. Improved Algorithms for Partial Curve Matching
  • Raimund Seidel, Victor Alvarez and David Kirkpatrick. Can Nearest Neighbor Searching be Simple and Always Fast?
  • Matthias Poloczek. Bounds on Greedy Algorithms for MAX SAT
  • Venkatesan Chakaravarthy, Amit Kumar, Sambuddha Roy and Yogish Sabharwal. Resource Allocation for Covering Time Varying Demands