| 2012 | A 5-Approximation for Capacitated Facility Location. Manisha Bansal, Naveen Garg, Neelima Gupta |
| 2012 | A Bicriteria Approximation for the Reordering Buffer Problem. Siddharth Barman, Shuchi Chawla, Seeun Umboh |
| 2012 | A Dual-Fitting $\frac{3}{2}$ -Approximation Algorithm for Some Minimum-Cost Graph Problems. James M. Davis, David P. Williamson |
| 2012 | A Fast and Simple Subexponential Fixed Parameter Algorithm for One-Sided Crossing Minimization. Yasuaki Kobayashi, Hisao Tamaki |
| 2012 | A Model for Minimizing Active Processor Time. Jessica Chang, Harold N. Gabow, Samir Khuller |
| 2012 | A Path-Decomposition Theorem with Applications to Pricing and Covering on Trees. Marek Cygan, Fabrizio Grandoni, Stefano Leonardi, Marcin Pilipczuk, Piotr Sankowski |
| 2012 | A Polynomial Kernel for Proper Interval Vertex Deletion. Fedor V. Fomin, Saket Saurabh, Yngve Villanger |
| 2012 | A Self-adjusting Data Structure for Multidimensional Point Sets. Eunhui Park, David M. Mount |
| 2012 | Algorithms - ESA 2012 - 20th Annual European Symposium, Ljubljana, Slovenia, September 10-12, 2012. Proceedings Leah Epstein, Paolo Ferragina |
| 2012 | An Experimental Study of Dynamic Dominators. Loukas Georgiadis, Giuseppe F. Italiano, Luigi Laura, Federico Santaroni |
| 2012 | Approximating Earliest Arrival Flows in Arbitrary Networks. Martin Groß, Jan-Philipp W. Kappmeier, Daniel R. Schmidt, Melanie Schmidt |
| 2012 | Approximation Algorithms for Wireless Link Scheduling with Flexible Data Rates. Thomas Kesselheim |
| 2012 | Approximation of Minimum Cost Homomorphisms. Pavol Hell, Monaldo Mastrolilli, Mayssam Mohammadi Nevisi, Arash Rafiey |
| 2012 | Average Case Analysis of Java 7's Dual Pivot Quicksort. Sebastian Wild, Markus E. Nebel |
| 2012 | Better Bounds for Graph Bisection. Daniel Delling, Renato Fonseca F. Werneck |
| 2012 | Bottleneck Non-crossing Matching in the Plane. A. Karim Abu-Affash, Paz Carmi, Matthew J. Katz, Yohai Trabelsi |
| 2012 | Colouring AT-Free Graphs. Dieter Kratsch, Haiko Müller |
| 2012 | Constructing Street Networks from GPS Trajectories. Mahmuda Ahmed, Carola Wenk |
| 2012 | Data Structures on Event Graphs. Bernard Chazelle, Wolfgang Mulzer |
| 2012 | Efficient Communication Protocols for Deciding Edit Distance. Hossein Jowhari |
| 2012 | Embedding Paths into Trees: VM Placement to Minimize Congestion. Debojyoti Dutta, Michael Kapralov, Ian Post, Rajendra Shinde |
| 2012 | Explicit and Efficient Hash Families Suffice for Cuckoo Hashing with a Stash. Martin Aumüller, Martin Dietzfelbinger, Philipp Woelfel |
| 2012 | Extending Partial Representations of Function Graphs and Permutation Graphs. Pavel Klavík, Jan Kratochvíl, Tomasz Krawczyk, Bartosz Walczak |
| 2012 | FPT Algorithms for Domination in Biclique-Free Graphs. Jan Arne Telle, Yngve Villanger |
| 2012 | Faster Geometric Algorithms via Dynamic Determinant Computation. Vissarion Fisikopoulos, Luis Mariano Peñaranda |
| 2012 | Finding Social Optima in Congestion Games with Positive Externalities. Bart de Keijzer, Guido Schäfer |
| 2012 | Hierarchical Hub Labelings for Shortest Paths. Ittai Abraham, Daniel Delling, Andrew V. Goldberg, Renato Fonseca F. Werneck |
| 2012 | I/O-efficient Hierarchical Diameter Approximation. Deepak Ajwani, Ulrich Meyer, David Veith |
| 2012 | Improved Distance Oracles and Spanners for Vertex-Labeled Graphs. Shiri Chechik |
| 2012 | Improved Implementation of Point Location in General Two-Dimensional Subdivisions. Michael Hemmer, Michal Kleinbort, Dan Halperin |
| 2012 | Induced Disjoint Paths in Claw-Free Graphs. Petr A. Golovach, Daniël Paulusma, Erik Jan van Leeuwen |
| 2012 | Kinetic Compressed Quadtrees in the Black-Box Model with Applications to Collision Detection for Low-Density Scenes. Mark de Berg, Marcel Roeloffzen, Bettina Speckmann |
| 2012 | Knowledge, Level of Symmetry, and Time of Leader Election. Emanuele G. Fusco, Andrzej Pelc |
| 2012 | Lines through Segments in 3D Space. Efi Fogel, Michael Hemmer, Asaf Porat, Dan Halperin |
| 2012 | Locally Correct Fréchet Matchings. Kevin Buchin, Maike Buchin, Wouter Meulemans, Bettina Speckmann |
| 2012 | Lower Bounds for Sorted Geometric Queries in the I/O Model. Peyman Afshani, Norbert Zeh |
| 2012 | Maximum Flow Networks for Stability Analysis of LEGO®Structures. Martin Waßmann, Karsten Weicker |
| 2012 | Maximum Multicommodity Flows over Time without Intermediate Storage. Martin Groß, Martin Skutella |
| 2012 | Minimum Average Distance Triangulations. László Kozma |
| 2012 | New Lower and Upper Bounds for Representing Sequences. Djamal Belazzougui, Gonzalo Navarro |
| 2012 | On Big Data Algorithmics. Yossi Matias |
| 2012 | On Computing Straight Skeletons by Means of Kinetic Triangulations. Peter Palfrader, Martin Held, Stefan Huber |
| 2012 | On Min-Power Steiner Tree. Fabrizio Grandoni |
| 2012 | On Online Labeling with Polynomially Many Labels. Martin Babka, Jan Bulánek, Vladimír Cunát, Michal Koucký, Michael E. Saks |
| 2012 | On the Complexity of Metric Dimension. Josep Díaz, Olli Pottonen, Maria J. Serna, Erik Jan van Leeuwen |
| 2012 | On the Value of Job Migration in Online Makespan Minimization. Susanne Albers, Matthias Hellwig |
| 2012 | Open Problems in Throughput Scheduling. Jirí Sgall |
| 2012 | Optimal Lower Bound for Differentially Private Multi-party Aggregation. T.-H. Hubert Chan, Elaine Shi, Dawn Song |
| 2012 | Optimizing Social Welfare for Network Bargaining Games in the Face of Unstability, Greed and Spite. T.-H. Hubert Chan, Fei Chen, Li Ning |
| 2012 | Optimizing over the Growing Spectrahedron. Joachim Giesen, Martin Jaggi, Sören Laue |
| 2012 | Parameterized Complexity of Induced H-Matching on Claw-Free Graphs. Danny Hermelin, Matthias Mnich, Erik Jan van Leeuwen |
| 2012 | Polynomial-Time Algorithms for Energy Games with Special Weight Structures. Krishnendu Chatterjee, Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai |
| 2012 | Polynomial-Time Approximation Schemes for Shortest Path with Alternatives. Tim Nonner |
| 2012 | Preemptive Coordination Mechanisms for Unrelated Machines. Fidaa Abed, Chien-Chung Huang |
| 2012 | Property Testing in Sparse Directed Graphs: Strong Connectivity and Subgraph-Freeness. Frank Hellweg, Christian Sohler |
| 2012 | Resource Buying Games. Tobias Harks, Britta Peis |
| 2012 | Revenue Guarantees in Sponsored Search Auctions. Ioannis Caragiannis, Christos Kaklamanis, Panagiotis Kanellopoulos, Maria Kyropoulou |
| 2012 | Routing Regardless of Network Stability. Bundit Laekhanukit, Adrian Vetta, Gordon T. Wilfong |
| 2012 | Simplifying Massive Contour Maps. Lars Arge, Lasse Deleuran, Thomas Mølhave, Morten Revsbæk, Jakob Truelsen |
| 2012 | Solving Simple Stochastic Games with Few Coin Toss Positions. Rasmus Ibsen-Jensen, Peter Bro Miltersen |
| 2012 | Span Programs and Quantum Algorithms for st-Connectivity and Claw Detection. Aleksandrs Belovs, Ben W. Reichardt |
| 2012 | Steiner Forest Orientation Problems. Marek Cygan, Guy Kortsarz, Zeev Nutov |
| 2012 | Succinct Data Structures for Path Queries. Meng He, J. Ian Munro, Gelin Zhou |
| 2012 | Succinct Posets. J. Ian Munro, Patrick K. Nicholson |
| 2012 | TSP Tours in Cubic Graphs: Beyond 4/3. José R. Correa, Omar Larré, José A. Soto |
| 2012 | The Clique Problem in Ray Intersection Graphs. Sergio Cabello, Jean Cardinal, Stefan Langerman |
| 2012 | The Quantum Query Complexity of Read-Many Formulas. Andrew M. Childs, Shelby Kimmel, Robin Kothari |
| 2012 | The Simplex Tree: An Efficient Data Structure for General Simplicial Complexes. Jean-Daniel Boissonnat, Clément Maria |
| 2012 | The Stretch Factor of L 1- and L ∞ -Delaunay Triangulations. Nicolas Bonichon, Cyril Gavoille, Nicolas Hanusse, Ljubomir Perkovic |
| 2012 | Time-Dependent Route Planning with Generalized Objective Functions. Gernot Veit Batz, Peter Sanders |
| 2012 | Two Dimensional Range Minimum Queries and Fibonacci Lattices. Gerth Stølting Brodal, Pooya Davoodi, Moshe Lewenstein, Rajeev Raman, S. Srinivasa Rao |
| 2012 | Weighted Geometric Set Multi-cover via Quasi-uniform Sampling. Nikhil Bansal, Kirk Pruhs |