Time-approximation trade-offs for inapproximable problems
From MaRDI portal
Recommendations
Cites work
- scientific article; zbMATH DE number 6474898 (Why is no real title available?)
- A lower bound for approximating the Grundy number
- An \(O(\log n/ \log \log n)\)-approximation algorithm for the asymmetric traveling salesman problem
- Analytical approach to parallel repetition
- Approximating the minimum maximal independence number
- Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms
- Approximation of min coloring by moderately exponential algorithms
- Capacitated domination faster than O(2ⁿ)
- Efficient approximation of Min Set Cover by moderately exponential algorithms
- Exact and approximate bandwidth
- Exponential-time approximation of weighted set cover
- Fast algorithms for min independent dominating set
- Fixed-Parameter and Approximation Algorithms: A New Look
- Lossy kernelization
- New inapproximability bounds for TSP
- On the hardness of approximating minimization problems
- On the worst-case performance of some algorithms for the asymmetric traveling salesman problem
- Parameterized approximation of dominating set problems
- Parameterized approximation via fidelity preserving transformations
- Some optimal inapproximability results
- Strong lower bounds on the approximability of some NPO PB-complete maximization problems
- The constant inapproximability of the parameterized dominating set problem
- The projection games conjecture and the NP-hardness of n-approximating Set-Cover
- Two-query PCP with subconstant error
- Which problems have strongly exponential complexity?
Cited in
(16)- From symmetry to asymmetry: generalizing TSP approximations by parametrization
- Grundy Distinguishes Treewidth from Pathwidth
- scientific article; zbMATH DE number 1226309 (Why is no real title available?)
- Time-approximation trade-offs for inapproximable problems
- From symmetry to asymmetry: generalizing TSP approximations by parametrization
- In)approximability of Maximum Minimal FVS
- Moderate exponential-time algorithms for scheduling problems
- Minimum stable cut and treewidth
- (In)approximability of maximum minimal FVS
- Grundy distinguishes treewidth from pathwidth
- New tools and connections for exponential-time approximation
- Parameterized max min feedback vertex set
- Introducing \textsf{lop}-kernels: a framework for kernelization lower bounds
- Improved (In-)Approximability Bounds for d-Scattered Set
- Efficient Algorithms for Asymptotic Bounds on Termination Time in VASS
- Moderate exponential-time algorithms for scheduling problems
This page was built for publication: Time-approximation trade-offs for inapproximable problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1678175)
