Exponential approximation schemata for some network design problems
type: Item
instance of: scholarly article
title: Exponential approximation schemata for some network design problems
zbMATH Open document ID: 1334.68300
author: Nicolas Boria
author: Nicolas Bourgeois
author: Bruno Escoffier
author: Vangelis Th. Paschos
published in: Journal of Discrete Algorithms
publication date: 2014-08-13T00:00:00Z
Mathematics Subject Classification ID: 68W25
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 90B10
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 90C35
zbMATH DE Number: 6329907
zbMATH Keywords: exponential algorithms
zbMATH Keywords: approximation algorithms
zbMATH Keywords: Steiner tree
zbMATH Keywords: traveling salesman problem
MaRDI profile type: Publication
full work available at URL: j.jda.2013.06.011
OpenAlex ID: W2079928809
cites work: Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
cites work: The traveling salesman problem and its variations
cites work: The Steiner problem with edge lengths 1 and 2
cites work: Exact algorithms for exact satisfiability and number of perfect matchings
cites work: Narrow sieves for parameterized paths and packings
cites work: Efficient approximation of Min Set Cover by moderately exponential algorithms
cites work: Approximation of min coloring by moderately exponential algorithms
cites work: Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms
cites work: An improved LP-based approximation for Steiner tree
cites work: Fixed-Parameter Approximation: Conceptual Framework and Approximability Results
cites work: Exponential-time approximation of weighted set cover
cites work: Exact and approximate bandwidth
cites work: Parameterized Approximation Problems
cites work: Parameterized approximation of dominating set problems
cites work: Faster Steiner Tree Computation in Polynomial-Space
cites work: An Exponential Time 2-Approximation Algorithm for Bandwidth
cites work: Expected Computation Time for Hamiltonian Path problem
cites work: A Dynamic Programming Approach to Sequencing Problems
cites work: Which problems have strongly exponential complexity?
cites work: Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs
cites work: Deterministic 7/8-Approximation for the Metric Maximum TSP
cites work: Saving space by algebraization
cites work: A Faster Algorithm for the Steiner Tree Problem
cites work: Approximation algorithms for the maximum Hamiltonian path problem with specified endpoint(s)
cites work: Fast Polynomial-Space Algorithms Using Möbius Inversion: Improving on Steiner Tree and Related Problems
cites work: A 7/9 - Approximation Algorithm for the Maximum Traveling Salesman Problem
cites work: The Traveling Salesman Problem with Distances One and Two
DOI: 10.1016/J.JDA.2013.06.011
description: scientific article; zbMATH DE number 6329907