skip to main content
Department of Computer Science University of Colorado Boulder
cu: home | engineering | mycuinfo | about | cu a-z | search cu | contact cu cs: about | calendar | directory | catalog | schedules | mobile | contact cs
home · the department · news · 

Gabow, Goemans, Tardos and Williamson Receive Glover-Klingman Prize


December 2010

Professor Harold (Hal) Gabow, Michel Goemans (MIT), Éva Tardos (Cornell University) and David Williamson (Cornell University) received the Glover-Klingman Prize for the best paper of the year published in Networks: An International Journal. The paper was titled "Approximating the smallest k-edge connected spanning subgraph by LP-rounding."

From the citation:

An important problem in network design is to identify a spanning subgraph that is k-edge connected and has the fewest number of edges. In this very nice contribution, the authors show that from an algorithmic perspective the problem gets easier to approximate as k increases, for both directed and undirected graphs. Specifically, the paper carefully analyzes an approximation algorithm based on rounding a linear programming relaxation of the problem. The authors also construct examples to show the tightness of their analysis of this algorithm and present an NP-hardness result to show that a better approximation is unlikely to exist.

The winners of this annual award are selected by the Editors-in-Chief, with assistance from members of the Editorial Board of the journal.

See also:
Department of Computer Science
College of Engineering and Applied Science
University of Colorado Boulder
Boulder, CO 80309-0430 USA
Send email to

Engineering Center Office Tower
ECOT 717
FAX +1-303-492-2844
XHTML 1.0/CSS2 ©2012 Regents of the University of Colorado
Privacy · Legal · Trademarks
May 5, 2012 (13:46)