Polynomial time approximation schemes for dense instances of NP-hard problems
From MaRDI portal
Publication:1305935
Recommendations
- scientific article; zbMATH DE number 1263204
- Polynomial time approximation schemes for some dense instances of NP-hard optimization problems
- Towards hardness of approximation for polynomial time problems
- Polynomial time approximation schemes and parameterized complexity
- Mathematical Foundations of Computer Science 2004
- Polynomial time approximation schemes for dense instances of minimum constraint satisfaction
- scientific article; zbMATH DE number 1839429
- On the efficiency of polynomial time approximation schemes
- Approximation algorithms for NP-hard problems
- scientific article; zbMATH DE number 1865680
Cites work
- A Chernoff Bound for Random Walks on Expander Graphs
- A new polynomial-time algorithm for linear programming
- A random polynomial-time algorithm for approximating the volume of convex bodies
- Approximate Algorithms for the 0/1 Knapsack Problem
- Approximating the Permanent
- Bin packing can be solved within 1+epsilon in linear time
- Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
- Hamiltonian circuits in random graphs
- scientific article; zbMATH DE number 3888913 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1256636 (Why is no real title available?)
- scientific article; zbMATH DE number 1559516 (Why is no real title available?)
- scientific article; zbMATH DE number 1559517 (Why is no real title available?)
- scientific article; zbMATH DE number 780787 (Why is no real title available?)
- scientific article; zbMATH DE number 845841 (Why is no real title available?)
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- MAX-CUT has a randomized approximation scheme in dense graphs
- Monte-Carlo approximation algorithms for enumeration problems
- On the Approximation of Maximum Satisfiability
- On the greedy algorithm for satisfiability
- On the hardness of approximating minimization problems
- Optimization, approximation, and complexity classes
- Polynomial time randomized approximation schemes for Tutte–Gröthendieck invariants: The dense case
- Probabilistic checking of proofs
- Probabilistic construction of deterministic algorithms: approximating packing integer programs
- Probability Inequalities for Sums of Bounded Random Variables
- Randomized rounding: A technique for provably good algorithms and algorithmic proofs
- Randomness in interactive proofs
- The complexity of colouring problems on dense graphs
- The Complexity of Multiterminal Cuts
- The Metropolis algorithm for graph bisection
- Traffic-light scheduling on the grid
Cited in
(59)- Exact and superpolynomial approximation algorithms for the \textsc{densest \textit{K}-subgraph} problem
- The approximability of maximum rooted triplets consistency with fan triplets and forbidden triplets
- On the weighted quartet consensus problem
- Polynomial approximation algorithms with performance guarantees: an introduction-by-example
- Improved approximations for max set splitting and max NAE SAT
- Improved approximation for spanning star forest in dense graphs
- In search of the densest subgraph
- An SDP randomized approximation algorithm for max hypergraph cut with limited unbalance
- Classical symmetries and the quantum approximate optimization algorithm
- The maximum exposure problem
- Domination chain: characterisation, classical complexity, parameterised complexity and approximability
- Additive approximation for edge-deletion problems
- On the \(k\)-edge-incident subgraph problem and its variants
- The complexity of detecting fixed-density clusters
- PTAS for densest \(k\)-subgraph in interval graphs
- Genus characterizes the complexity of certain graph problems: Some tight results
- On the complexity landscape of the domination chain
- Approximating subdense instances of covering problems
- The approximability of maximum rooted triplets consistency with fan triplets and forbidden triplets
- On variants of the spanning star forest problem
- Introduction to testing graph properties
- Approximation of the quadratic knapsack problem
- Approximation Algorithms for Geometric Intersection Graphs
- Parallel approximation to high multiplicity scheduling problemsVIAsmooth multi-valued quadratic programming
- Tight complexity bounds for FPT subgraph problems parameterized by the clique-width
- scientific article; zbMATH DE number 1263204 (Why is no real title available?)
- scientific article; zbMATH DE number 1301970 (Why is no real title available?)
- Polynomial time approximation schemes for dense instances of minimum constraint satisfaction
- Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : de la structure de NPO à la structure des instances
- Approximating vertex cover in dense hypergraphs
- On percolation and \(\mathcal{NP}\)-hardness
- Approximating \(k\)-generalized connectivity via collapsing HSTs
- Nearly tight approximation bounds for vertex cover on dense \(k\)-uniform \( k\)-partite hypergraphs
- Contribution of copositive formulations to the graph partitioning problem
- Sublinear-time Algorithms
- Introduction to testing graph properties
- Simplex transformations and the multiway cut problem
- Constrained assortment optimization under the paired combinatorial logit model
- A polynomial-time algorithm to determine (almost) Hamiltonicity of dense regular graphs
- scientific article; zbMATH DE number 7559431 (Why is no real title available?)
- Dynamic balanced graph partitioning
- Weighted upper edge cover: complexity and approximability
- Mathematical Foundations of Computer Science 2004
- Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
- On solving the densest \(k\)-subgraph problem on large graphs
- The Maximum Exposure Problem.
- Polynomial time approximation schemes for some dense instances of NP-hard optimization problems
- Semidefinite approximations for quadratic programs over orthogonal matrices
- Integer point sets minimizing average pairwise \(L_{1}\) distance: What is the optimal shape of a town?
- On the hardness and approximation of the densest k-subgraph problem in parameterized metric graphs
- A subquadratic bound for online bisection
- Dense graph partitioning on sparse and dense graphs
- Pliability and approximating Max-CSPs
- Exploiting dense structures in parameterized complexity
- Triangles improve 0.878 approximation for Maxcut
- Parameterized algorithms for editing to uniform cluster graph
- Fair and efficient cake division with connected pieces
- Approximate \(k\)-Steiner forests via the Lagrangian relaxation technique with internal preprocessing
- On the approximation of correlation clustering and consensus clustering
This page was built for publication: Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1305935)
