scientific article; zbMATH DE number 742977
From MaRDI portal
Publication:4763416
zbMath0818.90124MaRDI QIDQ4763416
Michel X. Goemans, David P. Williamson
Publication date: 11 April 1995
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
coveringshortest pathtraveling salesmanminimum spanning treeSteiner treegraph problemsapproximation techniqueminimum-weight perfect matching
Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27)
Related Items
A data structure for bicategories, with application to speeding up an approximation algorithm ⋮ New primal and dual matching heuristics ⋮ Approximating minimum-cost graph problems with spanning tree edges ⋮ A primal-dual approximation algorithm for generalized Steiner network problems ⋮ Approximation Algorithms for a Network Design Problem ⋮ The parsimonious property of cut covering problems and its applications ⋮ The point-to-point connection problem - analysis and algorithms ⋮ Rounding algorithms for covering problems ⋮ On the approximability of dense Steiner problems ⋮ The multi-weighted spanning tree problem ⋮ New approximation results on graph matching and related problems ⋮ A stabilized column generation scheme for the traveling salesman subtour problem ⋮ On Prize‐collecting Tours and the Asymmetric Travelling Salesman Problem ⋮ Primal-dual approximation algorithms for integral flow and multicut in trees, with applications to matching and set cover ⋮ Linear bounds for on-line Steiner problems ⋮ Exact methods for solving the elementary shortest and longest path problems ⋮ Survivable networks, linear programming relaxations and the parsimonious property ⋮ Online constrained forest and prize-collecting network design ⋮ On survivable network polyhedra ⋮ Modifying edges of a network to obtain short subgraphs ⋮ Approximation results for a min-max location-routing problem ⋮ Approximating the maximum internal spanning tree problem ⋮ A note on the subadditive network design problem ⋮ Fast and Simple Algorithms for Weighted Perfect Matching ⋮ A greedy heuristic for a minimum-weight forest problem
This page was built for publication:
