Exponential approximation schemata for some network design problems

DOI10.1016/J.JDA.2013.06.011MaRDI QIDQ396669zbMATH OpenOpenAlexFDO

Authors Nicolas Boria, Nicolas Bourgeois, Bruno Escoffier, Vangelis Th. Paschos

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

zbMATH Keywords

approximation algorithmstraveling salesman problemSteiner treeexponential algorithms

Mathematics Subject Classification ID

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)

Recommendations

• Moderately exponential approximation: bridging the gap between exact computation and polynomial approximation
• Moderately exponential approximation
• Efficient Approximation of Combinatorial Problems by Moderately Exponential Algorithms
• Moderately exponential time and fixed parameter approximation algorithms
• Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms

Cites work

• A 7/9 - Approximation Algorithm for the Maximum Traveling Salesman Problem
• A Dynamic Programming Approach to Sequencing Problems
• A Faster Algorithm for the Steiner Tree Problem
• An exponential time 2-approximation algorithm for bandwidth
• An improved LP-based approximation for Steiner tree
• Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs
• Approximation algorithms for the maximum Hamiltonian path problem with specified endpoint(s)
• Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms
• Approximation of min coloring by moderately exponential algorithms
• Deterministic 7/8-Approximation for the Metric Maximum TSP
• Efficient approximation of Min Set Cover by moderately exponential algorithms
• Exact algorithms for exact satisfiability and number of perfect matchings
• Exact and approximate bandwidth
• Expected Computation Time for Hamiltonian Path problem
• Exponential-time approximation of weighted set cover
• Fast Polynomial-Space Algorithms Using Möbius Inversion: Improving on Steiner Tree and Related Problems
• Faster Steiner Tree Computation in Polynomial-Space
• Fixed-Parameter Approximation: Conceptual Framework and Approximability Results
• Narrow sieves for parameterized paths and packings
• Parameterized Approximation Problems
• Parameterized approximation of dominating set problems
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• Saving space by algebraization
• The Steiner problem with edge lengths 1 and 2
• The Traveling Salesman Problem with Distances One and Two
• The traveling salesman problem and its variations
• Which problems have strongly exponential complexity?

Cited in

(3)

• scientific article; zbMATH DE number 3106147 (Why is no real title available?)
• When polynomial approximation meets exact computation
• When polynomial approximation meets exact computation

This page was built for publication: Exponential approximation schemata for some network design problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q396669)