Approximation schemes for NP-hard geometric optimization problems: a survey
From MaRDI portal
Publication:1403283
DOI10.1007/s10107-003-0438-yzbMath1035.90113OpenAlexW1520111182MaRDI QIDQ1403283
No author found.
Publication date: 1 September 2003
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10107-003-0438-y
Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02) Approximation algorithms (68W25)
Related Items (26)
On the minimum corridor connection problem and other generalized geometric problems ⋮ A $$(1+{\varepsilon })$$ ( 1 + ε ) -Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs ⋮ Approximation schemes for node-weighted geometric Steiner tree problems ⋮ Approximation schemes for Euclidean vehicle routing problems with time windows ⋮ Variational Approximation of Functionals Defined on 1-dimensional Connected Sets: The Planar Case ⋮ A Quasi-polynomial Time Approximation Scheme for Euclidean CVRPTW ⋮ Location, pricing and the problem of Apollonius ⋮ Literature reviews in operations research: a new taxonomy and a meta review ⋮ A convex approach to the Gilbert-Steiner problem ⋮ A Modern View on Stability of Approximation ⋮ Optimal transport methods for combinatorial optimization over two random point sets ⋮ A $(1+\varepsilon)$-Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs ⋮ Subsets of rectifiable curves in Hilbert space-the analyst's TSP ⋮ Polynomial-time approximation schemes for subset-connectivity problems in bounded-genus graphs ⋮ On single courier problem ⋮ A quasipolynomial time approximation scheme for Euclidean capacitated vehicle routing ⋮ Approximating the generalized minimum Manhattan network problem ⋮ Approximating minimum Manhattan networks in higher dimensions ⋮ Approximating minimum Steiner point trees in Minkowski planes ⋮ Dynamic programming approach to the generalized minimum Manhattan network problem ⋮ On the Computation of Kantorovich--Wasserstein Distances Between Two-Dimensional Histograms by Uncapacitated Minimum Cost Flows ⋮ Continuous reformulations and heuristics for the Euclidean travelling salesperson problem ⋮ Degree-bounded minimum spanning trees ⋮ Steiner intervals, geodesic intervals, and betweenness ⋮ Heuristic optimization for multi-depot vehicle routing problem in ATM network model ⋮ Polynomial Time Approximation Schemes for the Traveling Repairman and Other Minimum Latency Problems
Uses Software
This page was built for publication: Approximation schemes for NP-hard geometric optimization problems: a survey