| 2003 | Packing Steiner trees. | Kamal Jain, Mohammad Mahdian, Mohammad R. Salavatipour |
| 2003 | Algorithms for power savings. | Sandy Irani, Sandeep K. Shukla, Rajesh K. Gupta |
| 2003 | Better algorithms for high-dimensional proximity problems via asymmetric embeddings. | Piotr Indyk |
| 2003 | Directed graphs requiring large numbers of shortcuts. | William Hesse |
| 2003 | Binary space partitions for 3D subdivisions. | John Hershberger, Subhash Suri |
| 2003 | Optimal parallel selection. | Yijie Han |
| 2003 | Integrality ratio for group Steiner trees and directed steiner trees. | Eran Halperin, Guy Kortsarz, Robert Krauthgamer, Aravind Srinivasan, Nan Wang |
| 2003 | Unconditional proof of tightness of Johnson bound. | Venkatesan Guruswami, Igor E. Shparlinski |
| 2003 | Embeddings and non-approximability of geometric problems. | Venkatesan Guruswami, Piotr Indyk |
| 2003 | Counting inversions in lists. | Anupam Gupta, Francis Zane |
| 2003 | Improved results for directed multicut. | Anupam Gupta |
| 2003 | Zonotopes as bounding volumes. | Leonidas J. Guibas, An Thanh Nguyen, Li Zhang |
| 2003 | High-order entropy-compressed text indexes. | Roberto Grossi, Ankur Gupta, Jeffrey Scott Vitter |
| 2003 | An improved approximation algorithm for the partial latin square extension problem. | Carla P. Gomes, Rommel G. Regis, David B. Shmoys |
| 2003 | Competitiveness via consensus. | Andrew V. Goldberg, Jason D. Hartline |
| 2003 | Simultaneous optimization for concave costs: single sink aggregation or single source buy-at-bulk. | Ashish Goel, Deborah Estrin |
| 2003 | Approximation of functions over redundant dictionaries using coherence. | Anna C. Gilbert, S. Muthukrishnan, Martin Strauss |
| 2003 | The flow complex: a data structure for geometric modeling. | Joachim Giesen, Matthias John |
| 2003 | Computing strongly connected components in a linear number of symbolic steps. | Raffaella Gentilini, Carla Piazza, Alberto Policriti |
| 2003 | Better performance bounds for finding the smallest k-edge connected spanning subgraph of a multigraph. | Harold N. Gabow |
| 2003 | Perfect matchings in random graphs with prescribed minimal degree. | Alan M. Frieze, Boris G. Pittel |
| 2003 | Implicit dictionaries supporting searches and amortized updates in O(log n log log n) time. | Gianni Franceschini, Roberto Grossi |
| 2003 | Dominating sets in planar graphs: branch-width and exponential speed-up. | Fedor V. Fomin, Dimitrios M. Thilikos |
| 2003 | Minimum cost flows over time without intermediate storage. | Lisa Fleischer, Martin Skutella |
| 2003 | Approximately optimal control of fluid networks. | Lisa Fleischer, Jay Sethuraman |