Super-polynomial approximation branching algorithms

DOI10.1051/RO/2015060MaRDI QIDQ2954364zbMATH OpenOpenAlexFDO

Authors Bruno Escoffier, Vangelis Th. Paschos, Emeric Tourniaire

Publication date 12 January 2017

Published in RAIRO - Operations Research (Search for Journal in Brave)

Full work available at URL https://hal.sorbonne-universite.fr/hal-01432021/file/Escoffier_2016_Super-Polynomial.pdf

zbMATH Keywords

moderately exponential approximationbranching algorithmapproximation schema

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Recommendations

• Moderately exponential time and fixed parameter approximation algorithms
• Moderately exponential approximation: bridging the gap between exact computation and polynomial approximation
• Approximating optimum branchings in linear time
• Efficient Approximation of Combinatorial Problems by Moderately Exponential Algorithms
• Algorithms and Computation

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1330033 (Why is no real title available?)
• A measure \& conquer approach for the analysis of exact algorithms
• An exact algorithm for MAX-CUT in sparse graphs
• An exponential time 2-approximation algorithm for bandwidth
• Approximating MAX SAT by moderately exponential and parameterized algorithms
• Approximation algorithms for maximization problems arising in graph partitioning
• Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms
• Approximation of min coloring by moderately exponential algorithms
• Combining Two Worlds: Parameterised Approximation for Vertex Cover
• Efficient algorithms for the \textsc{max~\(k\)-vertex cover problem}
• Exact and approximate bandwidth
• Exact exponential algorithms.
• Finding induced subgraphs via minimal triangulations
• Fixed-Parameter Approximation: Conceptual Framework and Approximability Results
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Improved approximation algorithms for maximum graph partitioning problems
• MAX SAT approximation beyond the limits of polynomial-time approximation
• On Parameterized Approximability
• On the complexity of \(k\)-SAT
• Optimization, approximation, and complexity classes
• Parameterized Approximation Problems
• Parameterized approximation via fidelity preserving transformations
• Some optimal inapproximability results
• The importance of being biased
• Which problems have strongly exponential complexity?

Cited in

(3)

• Parallel machine scheduling with minimum number of tardy jobs: approximation and exponential algorithms
• Approximate min-sum subset convolution
• Approximate monotone local search for weighted problems

This page was built for publication: Super-polynomial approximation branching algorithms

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