Primal-Dual Approximation Algorithms for Feedback Problems in Planar Graphs

Similar content being viewed by others

New performance guarantees for the greedy maximization of submodular set functions

Article 10 May 2016

Set-Limited Functions and Polynomial-Time Interior-Point Methods

Article Open access 13 February 2023

Trigonometric approximation of the Max-Cut polytope is star-like

Article 03 February 2022

Author information

Authors and Affiliations

1. Dept. of Mathematics, M.I.T.; Cambridge, MA 02139; E-mail: goemans@math.mit.edu, , , , , , US

   Michel X. Goemans

2. IBM T.J. Watson Research Center; P.O. Box 218, Yorktown Heights, NY, 10598; E-mail: dpw@watson.ibm.com, , , , , , US

   David P. Williamson

Authors

1. Michel X. Goemans
   View author publications

   You can also search for this author in PubMed Google Scholar

2. David P. Williamson
   View author publications

   You can also search for this author in PubMed Google Scholar

Additional information

Received: August 22, 1996

Rights and permissions

Reprints and permissions

About this article

Cite this article

Goemans, M., Williamson, D. Primal-Dual Approximation Algorithms for Feedback Problems in Planar Graphs. Combinatorica 18, 37–59 (1998). https://doi.org/10.1007/PL00009810

Download citation

• Issue Date: January 1998

• DOI: https://doi.org/10.1007/PL00009810

• AMS Subject Classification (1991) Classes:  90C27, 05C85, 68Q25