scientific article; zbMATH DE number 1754594
From MaRDI portal
zbMath0986.90082MaRDI QIDQ4535019
Lars Engebretsen, Marek Karpinski
Publication date: 12 June 2002
Full work available at URL: http://link.springer.de/link/service/series/0558/bibs/2076/20760201
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
Differential approximation results for the traveling salesman and related problems, A $$(1+{\varepsilon })$$ ( 1 + ε ) -Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs, When the greedy algorithm fails, A $(1+\varepsilon)$-Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs, Affine reductions for LPs and SDPs, Restricted Common Superstring and Restricted Common Supersequence, Approximation algorithms for some vehicle routing problems, Approximation algorithms for the maximum Hamiltonian path problem with specified endpoint(s), Polynomial approximation algorithms with performance guarantees: an introduction-by-example, TSP with bounded metrics, Cooperative TSP, Differential approximation of NP-hard problems with equal size feasible solutions, Differential approximation results for the traveling salesman problem with distances 1 and 2