| 2007 | A 1.875: approximation algorithm for the stable marriage problem. Kazuo Iwama, Shuichi Miyazaki, Naoya Yamauchi |
| 2007 | A PTAS for TSP with neighborhoods among fat regions in the plane. Joseph S. B. Mitchell |
| 2007 | A divide and conquer algorithm for Moses Charikar, Konstantin Makarychev, Yury Makarychev |
| 2007 | A faster cache-oblivious shortest-path algorithm for undirected graphs with bounded edge lengths. Luca Allulli, Peter Lichodzijewski, Norbert Zeh |
| 2007 | A linear work, O(n Ioannis Koutis, Gary L. Miller |
| 2007 | A lower bound for scheduling mechanisms. George Christodoulou, Elias Koutsoupias, Angelina Vidali |
| 2007 | A near linear time constant factor approximation for Euclidean bichromatic matching (cost). Piotr Indyk |
| 2007 | A near-optimal algorithm for computing the entropy of a stream. Amit Chakrabarti, Graham Cormode, Andrew McGregor |
| 2007 | A network formation game for bipartite exchange economies. Eyal Even-Dar, Michael J. Kearns, Siddharth Suri |
| 2007 | A polynomial-time approximation scheme for Steiner tree in planar graphs. Glencora Borradaile, Claire Kenyon-Mathieu, Philip N. Klein |
| 2007 | A rigorous analysis of population stratification with limited data. Kamalika Chaudhuri, Eran Halperin, Satish Rao, Shuheng Zhou |
| 2007 | A simple storage scheme for strings achieving entropy bounds. Paolo Ferragina, Rossano Venturini |
| 2007 | Aggregation of partial rankings, Nir Ailon |
| 2007 | Algorithms and incentives for robust ranking. Rajat Bhattacharjee, Ashish Goel |
| 2007 | All-pairs bottleneck paths in vertex weighted graphs. Asaf Shapira, Raphael Yuster, Uri Zwick |
| 2007 | An algebraic algorithm for weighted linear matroid intersection. Nicholas J. A. Harvey |
| 2007 | An efficient cost-sharing mechanism for the prize-collecting Steiner forest problem. Anupam Gupta, Jochen Könemann, Stefano Leonardi, R. Ravi, Guido Schäfer |
| 2007 | An elementary construction of constant-degree expanders. Noga Alon, Oded Schwartz, Asaf Shapira |
| 2007 | An unbiased pointing operator for unlabeled structures, with applications to counting and sampling. Manuel Bodirsky, Éric Fusy, Mihyun Kang, Stefan Vigerske |
| 2007 | Analytic combinatorics: a calculus of discrete structures. Philippe Flajolet |
| 2007 | Approximate shortest paths in anisotropic regions. Siu-Wing Cheng, Hyeon-Suk Na, Antoine Vigneron, Yajun Wang |
| 2007 | Approximating entropy from sublinear samples. Mickey Brautbar, Alex Samorodnitsky |
| 2007 | Approximating the spanning star forest problem and its applications to genomic sequence alignment. C. Thach Nguyen, Jian Shen, Minmei Hou, Li Sheng, Webb Miller, Louxin Zhang |
| 2007 | Approximation algorithms for embedding general metrics into trees. Mihai Badoiu, Piotr Indyk, Anastasios Sidiropoulos |
| 2007 | Approximation algorithms for node-weighted buy-at-bulk network design. Chandra Chekuri, Mohammad Taghi Hajiaghayi, Guy Kortsarz, Mohammad R. Salavatipour |
| 2007 | Approximation algorithms for prize collecting forest problems with submodular penalty functions. Yogeshwer Sharma, Chaitanya Swamy, David P. Williamson |
| 2007 | Approximation algorithms for stochastic and risk-averse optimization. Aravind Srinivasan |
| 2007 | Approximation algorithms via contraction decomposition. Erik D. Demaine, Mohammad Taghi Hajiaghayi, Bojan Mohar |
| 2007 | Better online buffer management. Fei Li, Jay Sethuraman, Clifford Stein |
| 2007 | Buying cheap is expensive: hardness of non-parametric multi-product pricing. Patrick Briest, Piotr Krysta |
| 2007 | Cheap labor can be expensive. Ning Chen, Anna R. Karlin |
| 2007 | Combinatorial algorithms for web search engines: three success stories. Monika Henzinger |
| 2007 | Compacting cuts: a new linear formulation for minimum cut. Robert D. Carr, Goran Konjevod, Greg Little, Venkatesh Natarajan, Ojas Parekh |
| 2007 | Complexity of Delaunay triangulation for points on lower-dimensional polyhedra. Nina Amenta, Dominique Attali, Olivier Devillers |
| 2007 | Compressing rectilinear pictures and minimizing access control lists. David L. Applegate, Gruia Calinescu, David S. Johnson, Howard J. Karloff, Katrina Ligett, Jia Wang |
| 2007 | Considering suppressed packets improves buffer management in QoS switches. Matthias Englert, Matthias Westermann |
| 2007 | Convergence to approximate Nash equilibria in congestion games. Steve Chien, Alistair Sinclair |
| 2007 | Correlation decay and deterministic FPTAS for counting list-colorings of a graph. David Gamarnik, Dmitriy Katz |
| 2007 | Counting colors in boxes. Haim Kaplan, Natan Rubin, Micha Sharir, Elad Verbin |
| 2007 | Counting good truth assignments of random Andrea Montanari, Devavrat Shah |
| 2007 | Delaunay refinement for piecewise smooth complexes. Siu-Wing Cheng, Tamal K. Dey, Edgar A. Ramos |
| 2007 | Designing and learning optimal finite support auctions. Edith Elkind |
| 2007 | Deterministic pivoting algorithms for constrained ranking and clustering problems. Anke van Zuylen, Rajneesh Hegde, Kamal Jain, David P. Williamson |
| 2007 | Deterministic rendezvous, treasure hunts and strongly universal exploration sequences. Amnon Ta-Shma, Uri Zwick |
| 2007 | Digraph measures: Kelly decompositions, games, and orderings. Paul Hunter, Stephan Kreutzer |
| 2007 | Distributed algorithms for multicommodity flow problems via approximate steepest descent framework. Baruch Awerbuch, Rohit Khandekar, Satish Rao |
| 2007 | Dynamic pricing for impatient bidders. Nikhil Bansal, Ning Chen, Neva Cherniavsky, Atri Rudra, Baruch Schieber, Maxim Sviridenko |
| 2007 | Dynamic weighted ancestors. Tsvi Kopelowitz, Moshe Lewenstein |
| 2007 | Efficient aggregation algorithms for probabilistic data. T. S. Jayram, Satyen Kale, Erik Vee |
| 2007 | Efficient algorithms for computing all low Ramesh Hariharan, Telikepalli Kavitha, Debmalya Panigrahi |
| 2007 | Efficient contention resolution protocols for selfish agents. Amos Fiat, Yishay Mansour, Uri Nadav |
| 2007 | Efficient solutions to relaxations of combinatorial problems with submodular penalties via the Lovász extension and non-smooth convex optimization. Fabián A. Chudak, Kiyohito Nagano |
| 2007 | Efficient subspace approximation algorithms. Nariankadu D. Shyamalkumar, Kasturi R. Varadarajan |
| 2007 | Embedding metrics into ultrametrics and graphs into spanning trees with constant average distortion. Ittai Abraham, Yair Bartal, Ofer Neiman |
| 2007 | Energy efficient online deadline scheduling. Ho-Leung Chan, Wun-Tat Chan, Tak Wah Lam, Lap-Kei Lee, Kin-Sum Mak, Prudence W. H. Wong |
| 2007 | Equilibria in online games. Roee Engelberg, Joseph Naor |
| 2007 | Estimating the sortedness of a data stream. Parikshit Gopalan, T. S. Jayram, Robert Krauthgamer, Ravi Kumar |
| 2007 | Fast computation of power series solutions of systems of differential equations. Alin Bostan, Frédéric Chyzak, François Ollivier, Bruno Salvy, Éric Schost, Alexandre Sedoglavic |
| 2007 | Fast elimination of redundant linear equations and reconstruction of recombination-free mendelian inheritance on a pedigree. Jing Xiao, Lan Liu, Lirong Xia, Tao Jiang |
| 2007 | Faster dynamic matchings and vertex connectivity. Piotr Sankowski |
| 2007 | Finding a heaviest triangle is not harder than matrix multiplication. Artur Czumaj, Andrzej Lingas |
| 2007 | Fractional packing in ideal clutters. Yuji Matsuoka |
| 2007 | Games of fixed rank: a hierarchy of bimatrix games. Ravi Kannan, Thorsten Theobald |
| 2007 | Geometric and topological guarantees for the WRAP reconstruction algorithm. Edgar A. Ramos, Bardia Sadri |
| 2007 | Half integral packing, Erdős-Posá-property and graph minors. Ken-ichi Kawarabayashi |
| 2007 | Harmonic algorithm for 3-dimensional strip packing problem. Nikhil Bansal, Xin Han, Kazuo Iwama, Maxim Sviridenko, Guochuan Zhang |
| 2007 | Improved algorithms for path, matching, and packing problems. Jianer Chen, Songjian Lu, Sing-Hoi Sze, Fenghui Zhang |
| 2007 | Improved bounds for the online steiner tree problem in graphs of bounded edge-asymmetry. Spyros Angelopoulos |
| 2007 | Improved bounds for the symmetric rendezvous value on the line. Qiaoming Han, Donglei Du, Juan Carlos Vera, Luis Fernando Zuluaga |
| 2007 | Instability of FIFO in the permanent sessions model at arbitrarily small network loads. Matthew Andrews |
| 2007 | Island hopping and path colouring with applications to WDM network design. Andrew McGregor, F. Bruce Shepherd |
| 2007 | Layered multicast scheduling for the L Qingbo Cai, Vincenzo Liberatore |
| 2007 | Line-of-sight networks. Alan M. Frieze, Jon M. Kleinberg, R. Ravi, Warren Debany |
| 2007 | Linear programming relaxations of maxcut. Wenceslas Fernandez de la Vega, Claire Kenyon-Mathieu |
| 2007 | Lower bounds on average-case delay for video-on-demand broadcast protocols. Wei-Lung Dustin Tseng, David G. Kirkpatrick |
| 2007 | Making deterministic signatures quickly. Milan Ruzic |
| 2007 | Matrix scaling by network flow. Günter Rote, Martin Zachariasen |
| 2007 | Matrix-vector multiplication in sub-quadratic time: (some preprocessing required). Ryan Williams |
| 2007 | Matroids, secretary problems, and online mechanisms. Moshe Babaioff, Nicole Immorlica, Robert Kleinberg |
| 2007 | Maximum Jan M. Hochstein, Karsten Weihe |
| 2007 | Maximum independent sets in graphs of low degree. Vadim V. Lozin, Martin Milanic |
| 2007 | Maximum matching in graphs with an excluded minor. Raphael Yuster, Uri Zwick |
| 2007 | Minimizing movement. Erik D. Demaine, Mohammad Taghi Hajiaghayi, Hamid Mahini, Amin S. Sayedi-Roshkhar, Shayan Oveis Gharan, Morteza Zadimoghaddam |
| 2007 | Model-driven optimization using adaptive probes. Sudipto Guha, Kamesh Munagala |
| 2007 | Multiple choice tries and distributed hash tables. Luc Devroye, Gábor Lugosi, GaHyun Park, Wojciech Szpankowski |
| 2007 | Multiple source shortest paths in a genus g graph. Sergio Cabello, Erin W. Chambers |
| 2007 | Near-optimal algorithms for maximum constraint satisfaction problems. Moses Charikar, Konstantin Makarychev, Yury Makarychev |
| 2007 | Network sketching or: "How Much Geometry Hides in Connectivity?--Part II". Stefan Funke, Nikola Milosavljevic |
| 2007 | Noisy binary search and its applications. Richard M. Karp, Robert Kleinberg |
| 2007 | Obnoxious centers in graphs. Sergio Cabello, Günter Rote |
| 2007 | On Bregman Voronoi diagrams. Frank Nielsen, Jean-Daniel Boissonnat, Richard Nock |
| 2007 | On bounded leg shortest paths problems. Liam Roditty, Michael Segal |
| 2007 | On extremal subgraphs of random graphs. Graham R. Brightwell, Konstantinos Panagiotou, Angelika Steger |
| 2007 | On testable properties in bounded degree graphs. Artur Czumaj, Christian Sohler |
| 2007 | On the Liam Roditty |
| 2007 | On the bandwidth conjecture for 3-colourable graphs. Julia Böttcher, Mathias Schacht, Anusch Taraz |
| 2007 | On the number of tetrahedra with minimum, unit, and distinct volumes in three-space. Adrian Dumitrescu, Csaba D. Tóth |
| 2007 | On the separation and equivalence of paging strategies. Spyros Angelopoulos, Reza Dorrigiv, Alejandro López-Ortiz |
| 2007 | Online vertex colorings of random graphs without monochromatic subgraphs. Martin Marciniszyn, Reto Spöhel |
| 2007 | Optimal dynamic vertical ray shooting in rectilinear planar subdivisions. Yoav Giyora, Haim Kaplan |
| 2007 | Optimal scale-free compact routing schemes in networks of low doubling dimension. Goran Konjevod, Andréa W. Richa, Donglin Xia |
| 2007 | Optimization problems in multiple-interval graphs. Ayelet Butman, Danny Hermelin, Moshe Lewenstein, Dror Rawitz |
| 2007 | Path-independent load balancing with unreliable machines. James Aspnes, Yang Richard Yang, Yitong Yin |
| 2007 | Planar graphs are in 1-STRING. Jérémie Chalopin, Daniel Gonçalves, Pascal Ochem |
| 2007 | Polynomial approximation schemes for smoothed and random instances of multidimensional packing problems. David R. Karger, Krzysztof Onak |
| 2007 | Probabilistic analysis of linear programming decoding. Constantinos Daskalakis, Alexandros G. Dimakis, Richard M. Karp, Martin J. Wainwright |
| 2007 | Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007, New Orleans, Louisiana, USA, January 7-9, 2007 Nikhil Bansal, Kirk Pruhs, Clifford Stein |
| 2007 | Pull-based data broadcast with dependencies: be fair to users, not to items. Julien Robert, Nicolas Schabanel |
| 2007 | Quantum algorithm for a generalized hidden shift problem. Andrew M. Childs, Wim van Dam |
| 2007 | Quantum algorithms for Simon's problem over general groups. Gorjan Alagic, Cristopher Moore, Alexander Russell |
| 2007 | Randomization does not help searching predecessors. Mihai Patrascu, Mikkel Thorup |
| 2007 | Reconstruction using witness complexes. Leonidas J. Guibas, Steve Oudot |
| 2007 | Region-fault tolerant geometric spanners. Mohammad Ali Abam, Mark de Berg, Mohammad Farshi, Joachim Gudmundsson |
| 2007 | Resilient search trees. Irene Finocchi, Fabrizio Grandoni, Giuseppe F. Italiano |
| 2007 | Restricted strip covering and the sensor cover problem. Adam L. Buchsbaum, Alon Efrat, Shaili Jain, Suresh Venkatasubramanian, Ke Yi |
| 2007 | Sandpile transience on the grid is polynomially bounded. László Babai, Igor Gorodezky |
| 2007 | Scrambling adversarial errors using few random bits, optimal information reconciliation, and better private codes. Adam D. Smith |
| 2007 | Semi-oblivious routing: lower bounds. Mohammad Taghi Hajiaghayi, Robert Kleinberg, Tom Leighton |
| 2007 | Setting lower bounds on truthfulness: extended abstract. Ahuva Mu'alem, Michael Schapira |
| 2007 | Single source multiroute flows and cuts on uniform capacity networks. Henning Bruhn, Jakub Cerný, Alexander Hall, Petr Kolman |
| 2007 | Spectral clustering with limited independence. Anirban Dasgupta, John E. Hopcroft, Ravi Kannan, Pradipta Prometheus Mitra |
| 2007 | Speed scaling for weighted flow time. Nikhil Bansal, Kirk Pruhs, Clifford Stein |
| 2007 | Squarepants in a tree: sum of subtree clustering and hyperbolic pants decomposition. David Eppstein |
| 2007 | Strong price of anarchy. Nir Andelman, Michal Feldman, Yishay Mansour |
| 2007 | Succinct indexes for strings, binary relations and multi-labeled trees. Jérémy Barbay, Meng He, J. Ian Munro, S. Srinivasa Rao |
| 2007 | Testing for a theta. Maria Chudnovsky, Paul D. Seymour |
| 2007 | The Daniel Fernholz, Vijaya Ramachandran |
| 2007 | The approximation complexity of win-lose games. Xi Chen, Shang-Hua Teng, Paul Valiant |
| 2007 | The communication and streaming complexity of computing the longest common and increasing subsequences. Xiaoming Sun, David P. Woodruff |
| 2007 | The effectiveness of Stackelberg strategies and tolls for network congestion games. Chaitanya Swamy |
| 2007 | The independent even factor problem. Satoru Iwata, Kenjiro Takazawa |
| 2007 | The quantum Schur and Clebsch-Gordan transforms: I. efficient qudit circuits. Dave Bacon, Isaac L. Chuang, Aram W. Harrow |
| 2007 | The random graph threshold for Julie Anne Cain, Peter Sanders, Nicholas C. Wormald |
| 2007 | Torpid mixing of local Markov chains on 3-colorings of the discrete torus. David J. Galvin, Dana Randall |
| 2007 | Tree exploration with logarithmic memory. Leszek Gasieniec, Andrzej Pelc, Tomasz Radzik, Xiaohui Zhang |
| 2007 | Ultra-succinct representation of ordered trees. Jesper Jansson, Kunihiko Sadakane, Wing-Kin Sung |
| 2007 | Whole genome duplications, multi-break rearrangements, and genome halving problem. Max A. Alekseyev, Pavel A. Pevzner |
| 2007 | Worst case and probabilistic analysis of the 2-Opt algorithm for the TSP: extended abstract. Matthias Englert, Heiko Röglin, Berthold Vöcking |
| 2007 | Zone diagrams: existence, uniqueness and algorithmic challenge. Tetsuo Asano, Jirí Matousek, Takeshi Tokuyama |
| 2007 | k-means++: the advantages of careful seeding. David Arthur, Sergei Vassilvitskii |