Super-polynomial approximation branching algorithms
From MaRDI portal
Publication:2954364
DOI10.1051/ro/2015060zbMath1401.68360OpenAlexW2546937658MaRDI QIDQ2954364
Emeric Tourniaire, Bruno Escoffier, Vangelis Th. Paschos
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
Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Approximation algorithms (68W25)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms
- Efficient algorithms for the \textsc{max~\(k\)-vertex cover problem}
- Exact exponential algorithms.
- Exact and approximate bandwidth
- Improved approximation algorithms for maximum graph partitioning problems
- Approximation of min coloring by moderately exponential algorithms
- Optimization, approximation, and complexity classes
- Which problems have strongly exponential complexity?
- On subexponential and FPT-time inapproximability
- An exact algorithm for MAX-CUT in sparse graphs
- Approximation Algorithms for Maximization Problems Arising in Graph Partitioning
- Parameterized Approximation via Fidelity Preserving Transformations
- Approximating MAX SAT by Moderately Exponential and Parameterized Algorithms
- Combining Two Worlds: Parameterised Approximation for Vertex Cover
- Finding Induced Subgraphs via Minimal Triangulations
- A measure & conquer approach for the analysis of exact algorithms
- Fixed-Parameter Approximation: Conceptual Framework and Approximability Results
- On Parameterized Approximability
- Parameterized Approximation Problems
- The importance of being biased
- An Exponential Time 2-Approximation Algorithm for Bandwidth
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Some optimal inapproximability results
- On the complexity of \(k\)-SAT
- MAX SAT approximation beyond the limits of polynomial-time approximation
This page was built for publication: Super-polynomial approximation branching algorithms
