Exponential approximation schemata for some network design problems
From MaRDI portal
Publication:396669
DOI10.1016/J.JDA.2013.06.011zbMath1334.68300OpenAlexW2079928809MaRDI QIDQ396669
Nicolas Bourgeois, Vangelis Th. Paschos, Nicolas Boria, Bruno Escoffier
Publication date: 13 August 2014
Published in: Journal of Discrete Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jda.2013.06.011
Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Deterministic network models in operations research (90B10) Combinatorial optimization (90C27) Approximation algorithms (68W25)
Related Items (2)
When polynomial approximation meets exact computation ⋮ When polynomial approximation meets exact computation
Cites Work
- Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms
- Approximation algorithms for the maximum Hamiltonian path problem with specified endpoint(s)
- Exact and approximate bandwidth
- Exact algorithms for exact satisfiability and number of perfect matchings
- Parameterized approximation of dominating set problems
- Approximation of min coloring by moderately exponential algorithms
- Exponential-time approximation of weighted set cover
- Efficient approximation of Min Set Cover by moderately exponential algorithms
- The Steiner problem with edge lengths 1 and 2
- Which problems have strongly exponential complexity?
- The traveling salesman problem and its variations
- Narrow sieves for parameterized paths and packings
- Saving space by algebraization
- An improved LP-based approximation for steiner tree
- Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
- A Dynamic Programming Approach to Sequencing Problems
- Fixed-Parameter Approximation: Conceptual Framework and Approximability Results
- Parameterized Approximation Problems
- Faster Steiner Tree Computation in Polynomial-Space
- Deterministic 7/8-Approximation for the Metric Maximum TSP
- Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs
- Fast Polynomial-Space Algorithms Using Möbius Inversion: Improving on Steiner Tree and Related Problems
- A 7/9 - Approximation Algorithm for the Maximum Traveling Salesman Problem
- An Exponential Time 2-Approximation Algorithm for Bandwidth
- Expected Computation Time for Hamiltonian Path problem
- The Traveling Salesman Problem with Distances One and Two
- A Faster Algorithm for the Steiner Tree Problem
This page was built for publication: Exponential approximation schemata for some network design problems
