When polynomial approximation meets exact computation

DOI10.1007/S10479-018-2986-9MaRDI QIDQ5915964zbMATH OpenOpenAlexWikidataFDO

Authors Vangelis Th. Paschos

Publication date 6 March 2019

Published in Annals of Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10479-018-2986-9

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25)

Recommendations

• When polynomial approximation meets exact computation
• Moderately exponential approximation: bridging the gap between exact computation and polynomial approximation
• Moderately exponential approximation
• Preface
• Polynomial approximation algorithms with performance guarantees: an introduction-by-example

Cites work

• A 7/9 - Approximation Algorithm for the Maximum Traveling Salesman Problem
• A Dynamic Programming Approach to Sequencing Problems
• Approximating MAX SAT by moderately exponential and parameterized algorithms
• Approximating the minimum maximal independence number
• Approximation algorithms for combinatorial problems
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Approximation and Online Algorithms
• Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms
• Automata, Languages and Programming
• Capacitated domination faster than \(O(2^{n })\)
• Efficient approximation of Min Set Cover by moderately exponential algorithms
• Enumerating maximal independent sets with applications to graph colouring.
• Exact algorithms for exact satisfiability and number of perfect matchings
• Exact Algorithms for Maximum Independent Set
• Exact and approximate bandwidth
• Exact exponential algorithms.
• Expected Computation Time for Hamiltonian Path problem
• Exponential approximation schemata for some network design problems
• Exponential-time approximation of weighted set cover
• Fast algorithms for min independent dominating set
• scientific article; zbMATH DE number 3758364 (Why is no real title available?)
• scientific article; zbMATH DE number 1330033 (Why is no real title available?)
• scientific article; zbMATH DE number 1953201 (Why is no real title available?)
• scientific article; zbMATH DE number 2221549 (Why is no real title available?)
• Linear degree extractors and the inapproximability of max clique and chromatic number
• MAX SAT approximation beyond the limits of polynomial-time approximation
• On approximation properties of the Independent set problem for degree 3 graphs
• Optimization, approximation, and complexity classes
• Proof verification and the hardness of approximation problems
• Set partitioning via inclusion-exclusion
• The PCP theorem by gap amplification
• The projection games conjecture and the NP-hardness of n-approximating Set-Cover
• Vertex packings: Structural properties and algorithms
• When polynomial approximation meets exact computation

Cited in

(7)

• Highly resilient correctors for polynomials
• Master-slave strategy and polynomial approximation
• Moderately exponential approximation
• scientific article; zbMATH DE number 5124811 (Why is no real title available?)
• Very accurate estimates of the polygamma functions
• Moderately exponential approximation: bridging the gap between exact computation and polynomial approximation
• When polynomial approximation meets exact computation

This page was built for publication: When polynomial approximation meets exact computation

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