| 2003 | A (1+epsilon)-approximation algorithm for partitioning hypergraphs using a new algorithmic version of the Lovász Local Lemma. Mohammad R. Salavatipour |
| 2003 | A 5/4-approximation algorithm for minimum 2-edge-connectivity. Raja Jothi, Balaji Raghavachari, Subramanian Varadarajan |
| 2003 | A combinatorial algorithm for computing a maximum independent set in a t-perfect graph. Friedrich Eisenbrand, Stefan Funke, Naveen Garg, Jochen Könemann |
| 2003 | A faster and simpler fully dynamic transitive closure. Liam Roditty |
| 2003 | A new approximation algorithm for the asymmetric TSP with triangle inequality. Markus Bläser |
| 2003 | A note on the set systems used for broadcast encryption. Ravi Kumar, Alexander Russell |
| 2003 | A spectral technique for random satisfiable 3CNF formulas. Abraham Flaxman |
| 2003 | Algorithms for k-colouring and finding maximal independent sets. Jesper Makholm Byskov |
| 2003 | Algorithms for power savings. Sandy Irani, Sandeep K. Shukla, Rajesh K. Gupta |
| 2003 | Allocating vertex pi-guards in simple polygons via pseudo-triangulations. Bettina Speckmann, Csaba D. Tóth |
| 2003 | An approximate truthful mechanism for combinatorial auctions with single parameter agents. Aaron Archer, Christos H. Papadimitriou, Kunal Talwar, Éva Tardos |
| 2003 | An approximation algorithm for cutting out convex polygons. Adrian Dumitrescu |
| 2003 | An improved approximation algorithm for the 0-extension problem. Jittat Fakcharoenphol, Chris Harrelson, Satish Rao, Kunal Talwar |
| 2003 | An improved approximation algorithm for the partial latin square extension problem. Carla P. Gomes, Rommel G. Regis, David B. Shmoys |
| 2003 | Approximately optimal control of fluid networks. Lisa Fleischer, Jay Sethuraman |
| 2003 | Approximating asymmetric maximum TSP. Moshe Lewenstein, Maxim Sviridenko |
| 2003 | Approximation algorithm for embedding metrics into a two-dimensional space. Mihai Badoiu |
| 2003 | Approximation of functions over redundant dictionaries using coherence. Anna C. Gilbert, S. Muthukrishnan, Martin Strauss |
| 2003 | Better algorithms for high-dimensional proximity problems via asymmetric embeddings. Piotr Indyk |
| 2003 | Better performance bounds for finding the smallest k-edge connected spanning subgraph of a multigraph. Harold N. Gabow |
| 2003 | Between O(nm) and O(n alpha). Dieter Kratsch, Jeremy P. Spinrad |
| 2003 | Binary space partitions for 3D subdivisions. John Hershberger, Subhash Suri |
| 2003 | Browsing around a digital library. Ian H. Witten |
| 2003 | Certifying algorithms for recognizing interval graphs and permutation graphs. Dieter Kratsch, Ross M. McConnell, Kurt Mehlhorn, Jeremy P. Spinrad |
| 2003 | Certifying and repairing solutions to large LPs how good are LP-solvers? Marcel Dhiflaoui, Stefan Funke, Carsten Kwappik, Kurt Mehlhorn, Michael Seel, Elmar Schömer, Ralph Schulte, Dennis Weber |
| 2003 | Chain decompositions and independent trees in 4-connected graphs. Sean Curran, Orlando Lee, Xingxing Yu |
| 2003 | Compact representations of separable graphs. Daniel K. Blandford, Guy E. Blelloch, Ian A. Kash |
| 2003 | Comparing top k lists. Ronald Fagin, Ravi Kumar, D. Sivakumar |
| 2003 | Competitive queueing policies for QoS switches. Nir Andelman, Yishay Mansour, An Zhu |
| 2003 | Competitiveness via consensus. Andrew V. Goldberg, Jason D. Hartline |
| 2003 | Computing homotopic shortest paths in the plane. Sergei Bespamyatnikh |
| 2003 | Computing strongly connected components in a linear number of symbolic steps. Raffaella Gentilini, Carla Piazza, Alberto Policriti |
| 2003 | Counting inversions in lists. Anupam Gupta, Francis Zane |
| 2003 | Data migration to minimize the average completion time. Yoo Ah Kim |
| 2003 | Data streams: algorithms and applications. S. Muthukrishnan |
| 2003 | Deterministic identity testing for multivariate polynomials. Richard J. Lipton, Nisheeth K. Vishnoi |
| 2003 | Directed graphs requiring large numbers of shortcuts. William Hesse |
| 2003 | Directed scale-free graphs. Béla Bollobás, Christian Borgs, Jennifer T. Chayes, Oliver Riordan |
| 2003 | Dominating sets in planar graphs: branch-width and exponential speed-up. Fedor V. Fomin, Dimitrios M. Thilikos |
| 2003 | Dynamic TCP acknowledgement: penalizing long delays. Susanne Albers, Helge Bals |
| 2003 | Dynamic construction of Bluetooth scatternets of fixed degree and low diameter. Lali Barrière, Pierre Fraigniaud, Lata Narayanan, Jaroslav Opatrny |
| 2003 | Dynamic generators of topologically embedded graphs. David Eppstein |
| 2003 | Dynamic routing on networks with fixed-size buffers. William Aiello, Rafail Ostrovsky, Eyal Kushilevitz, Adi Rosén |
| 2003 | Edge disjoint paths revisited. Chandra Chekuri, Sanjeev Khanna |
| 2003 | Efficient sequences of trials. Edith Cohen, Amos Fiat, Haim Kaplan |
| 2003 | Embedding k-outerplanar graphs into l1. Chandra Chekuri, Anupam Gupta, Ilan Newman, Yuri Rabinovich, Alistair Sinclair |
| 2003 | Embeddings and non-approximability of geometric problems. Venkatesan Guruswami, Piotr Indyk |
| 2003 | Equitable colorings with constant number of colors. Sriram V. Pemmaraju, Kittikorn Nakprasit, Alexandr V. Kostochka |
| 2003 | Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons. Devdatt P. Dubhashi, Alessandro Mei, Alessandro Panconesi, Jaikumar Radhakrishnan, Aravind Srinivasan |
| 2003 | Faster approximation algorithms for the minimum latency problem. Aaron Archer, David P. Williamson |
| 2003 | Fault-tolerant facility location. Chaitanya Swamy, David B. Shmoys |
| 2003 | Fully-dynamic two dimensional orthogonal range and line segment intersection reporting in logarithmic time. Christian Worm Mortensen |
| 2003 | Graded conforming Delaunay tetrahedralization with bounded radius-edge ratio. Siu-Wing Cheng, Sheung-Hung Poon |
| 2003 | High-order entropy-compressed text indexes. Roberto Grossi, Ankur Gupta, Jeffrey Scott Vitter |
| 2003 | Implicit dictionaries supporting searches and amortized updates in O(log n log log n) time. Gianni Franceschini, Roberto Grossi |
| 2003 | Improved bounds on the average length of longest common subsequences. George S. Lueker |
| 2003 | Improved results for directed multicut. Anupam Gupta |
| 2003 | Inferring tree topologies using flow tests. S. Muthukrishnan, Torsten Suel, Radek Vingralek |
| 2003 | Inplace 2D matching in compressed images. Amihood Amir, Gad M. Landau, Dina Sokol |
| 2003 | Integrality ratio for group Steiner trees and directed steiner trees. Eran Halperin, Guy Kortsarz, Robert Krauthgamer, Aravind Srinivasan, Nan Wang |
| 2003 | Labeling schemes for small distances in trees. Stephen Alstrup, Philip Bille, Theis Rauhe |
| 2003 | Lower bounds for collusion-secure fingerprinting. Chris Peikert, Abhi Shelat, Adam D. Smith |
| 2003 | Lower bounds for embedding edit distance into normed spaces. Alexandr Andoni, Michel Deza, Anupam Gupta, Piotr Indyk, Sofya Raskhodnikova |
| 2003 | Lower bounds for external memory dictionaries. Gerth Stølting Brodal, Rolf Fagerberg |
| 2003 | Maintaining all-pairs approximate shortest paths under deletion of edges. Surender Baswana, Ramesh Hariharan, Sandeep Sen |
| 2003 | Matching planar maps. Helmut Alt, Alon Efrat, Günter Rote, Carola Wenk |
| 2003 | Minimizing weighted flow time. Nikhil Bansal, Kedar Dhamdhere |
| 2003 | Minimum cost flows over time without intermediate storage. Lisa Fleischer, Martin Skutella |
| 2003 | Multi-embedding and path approximation of metric spaces. Yair Bartal, Manor Mendel |
| 2003 | Multidimensional matching and fast search in suffix trees. Richard Cole, Moshe Lewenstein |
| 2003 | Multirate rearrangeable clos networks and a generalized edge coloring problem on bipartite graphs. Hung Q. Ngo, Van H. Vu |
| 2003 | Möbius-invariant natural neighbor interpolation. Marshall W. Bern, David Eppstein |
| 2003 | Non-independent randomized rounding. Benjamin Doerr |
| 2003 | On AC Mikkel Thorup |
| 2003 | On the combinatorial complexity of euclidean Voronoi cells and convex hulls of d-dimensional spheres. Jean-Daniel Boissonnat, Menelaos I. Karavelas |
| 2003 | On the complexity of distance-based evolutionary tree reconstruction. Valerie King, Li Zhang, Yunhong Zhou |
| 2003 | On the performance of user equilibria in traffic networks. Andreas S. Schulz, Nicolás E. Stier Moses |
| 2003 | On the rectilinear crossing number of complete graphs. Uli Wagner |
| 2003 | Online learning in online auctions. Avrim Blum, Vijay Kumar, Atri Rudra, Felix Wu |
| 2003 | Online paging with arbitrary associativity. Enoch Peserico |
| 2003 | Optimal parallel selection. Yijie Han |
| 2003 | Optimizing misdirection. Piotr Berman, Piotr Krysta |
| 2003 | Packing Steiner trees. Kamal Jain, Mohammad Mahdian, Mohammad R. Salavatipour |
| 2003 | Pass efficient algorithms for approximating large matrices. Petros Drineas, Ravi Kannan |
| 2003 | Perfect matchings in random graphs with prescribed minimal degree. Alan M. Frieze, Boris G. Pittel |
| 2003 | Perturbations and vertex removal in a 3D delaunay triangulation. Olivier Devillers, Monique Teillaud |
| 2003 | Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, January 12-14, 2003, Baltimore, Maryland, USA. |
| 2003 | Property testing of data dimensionality. Robert Krauthgamer, Ori Sasson |
| 2003 | Pursuit-evasion with imprecise target location. Günter Rote |
| 2003 | Quantum algorithms for some hidden shift problems. Wim van Dam, Sean Hallgren, Lawrence Ip |
| 2003 | Quantum property testing. Harry Buhrman, Lance Fortnow, Ilan Newman, Hein Röhrig |
| 2003 | Quick and good facility location. Mikkel Thorup |
| 2003 | Random MAX SAT, random MAX CUT, and their phase transitions. Don Coppersmith, David Gamarnik, Mohammad Taghi Hajiaghayi, Gregory B. Sorkin |
| 2003 | Random walks on the vertices of transportation polytopes with constant number of sources. Mary Cryan, Martin E. Dyer, Haiko Müller, Leen Stougie |
| 2003 | Rangesum histograms. S. Muthukrishnan, Martin Strauss |
| 2003 | Root comparison techniques applied to computing the additively weighted Voronoi diagram. Menelaos I. Karavelas, Ioannis Z. Emiris |
| 2003 | Scheduling techniques for media-on-demand. Amotz Bar-Noy, Richard E. Ladner, Tami Tamir |
| 2003 | Selection with monotone comparison cost. Sampath Kannan, Sanjeev Khanna |
| 2003 | Simultaneous optimization for concave costs: single sink aggregation or single source buy-at-bulk. Ashish Goel, Deborah Estrin |
| 2003 | Skip graphs. James Aspnes, Gauri Shah |
| 2003 | Smaller core-sets for balls. Mihai Badoiu, Kenneth L. Clarkson |
| 2003 | Smaller explicit superconcentrators. Noga Alon, Michael R. Capalbo |
| 2003 | Space-efficient finger search on degree-balanced search trees. Guy E. Blelloch, Bruce M. Maggs, Shan Leung Maverick Woo |
| 2003 | Sparse distance preservers and additive spanners. Béla Bollobás, Don Coppersmith, Michael Elkin |
| 2003 | Straight-skeleton based contour interpolation. Gill Barequet, Michael T. Goodrich, Aya Levi-Steiner, Dvir Steiner |
| 2003 | Sublinear-time approximation of Euclidean minimum spanning tree. Artur Czumaj, Funda Ergün, Lance Fortnow, Avner Magen, Ilan Newman, Ronitt Rubinfeld, Christian Sohler |
| 2003 | Sublogarithmic approximation for telephone multicast: path out of jungle. Michael Elkin, Guy Kortsarz |
| 2003 | The cover time of sparse random graphs. Colin Cooper, Alan M. Frieze |
| 2003 | The flow complex: a data structure for geometric modeling. Joachim Giesen, Matthias John |
| 2003 | The k-traveling repairman problem. Jittat Fakcharoenphol, Chris Harrelson, Satish Rao |
| 2003 | The set-associative cache performance of search trees. James D. Fix |
| 2003 | The similarity metric. Ming Li, Xin Chen, Xin Li, Bin Ma, Paul M. B. Vitányi |
| 2003 | Unconditional proof of tightness of Johnson bound. Venkatesan Guruswami, Igor E. Shparlinski |
| 2003 | Wavelength assignment and generalized interval graph coloring. Peter Winkler, Lisa Zhang |
| 2003 | Who cares about permanents? Persi Diaconis |
| 2003 | Zonotopes as bounding volumes. Leonidas J. Guibas, An Thanh Nguyen, Li Zhang |