Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
From MaRDI portal
Publication:1305935
DOI10.1006/jcss.1998.1605zbMath0937.68160OpenAlexW2065641139WikidataQ56387952 ScholiaQ56387952MaRDI QIDQ1305935
Sanjeev Arora, Marek Karpinski, David R. Karger
Publication date: 17 February 2000
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/jcss.1998.1605
Related Items
The maximum exposure problem, Improved approximations for max set splitting and max NAE SAT, Approximate \(k\)-Steiner forests via the Lagrangian relaxation technique with internal preprocessing, Approximation of the Quadratic Knapsack Problem, Genus characterizes the complexity of certain graph problems: Some tight results, Additive approximation for edge-deletion problems, Constrained Assortment Optimization Under the Paired Combinatorial Logit Model, A Polynomial-Time Algorithm to Determine (Almost) Hamiltonicity of Dense Regular Graphs, The Approximability of Maximum Rooted Triplets Consistency with Fan Triplets and Forbidden Triplets, Semidefinite approximations for quadratic programs over orthogonal matrices, Domination chain: characterisation, classical complexity, parameterised complexity and approximability, Tight complexity bounds for FPT subgraph problems parameterized by the clique-width, Exact and superpolynomial approximation algorithms for the \textsc{densest \textit{K}-subgraph} problem, Integer point sets minimizing average pairwise \(L_{1}\) distance: What is the optimal shape of a town?, Approximation Algorithms for Geometric Intersection Graphs, Improved approximation for spanning star forest in dense graphs, Parallel approximation to high multiplicity scheduling problemsVIAsmooth multi-valued quadratic programming, Approximating vertex cover in dense hypergraphs, Dynamic Balanced Graph Partitioning, Introduction to Testing Graph Properties, On the \(k\)-edge-incident subgraph problem and its variants, On the approximation of correlation clustering and consensus clustering, The approximability of maximum rooted triplets consistency with fan triplets and forbidden triplets, On percolation and ‐hardness, Approximating \(k\)-generalized connectivity via collapsing HSTs, Nearly tight approximation bounds for vertex cover on dense \(k\)-uniform \( k\)-partite hypergraphs, The Maximum Exposure Problem., On the weighted quartet consensus problem, On Variants of the Spanning Star Forest Problem, Contribution of copositive formulations to the graph partitioning problem, In search of the densest subgraph, Polynomial approximation algorithms with performance guarantees: an introduction-by-example, Sublinear-time Algorithms, An SDP randomized approximation algorithm for max hypergraph cut with limited unbalance, The complexity of detecting fixed-density clusters, Unnamed Item, On the Complexity Landscape of the Domination Chain, Weighted Upper Edge Cover: Complexity and Approximability, Introduction to Testing Graph Properties, Simplex Transformations and the Multiway Cut Problem, Approximating Subdense Instances of Covering Problems, Fair and efficient cake division with connected pieces, On solving the densestk-subgraph problem on large graphs, Classical symmetries and the quantum approximate optimization algorithm, PTAS for densest \(k\)-subgraph in interval graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A new polynomial-time algorithm for linear programming
- The complexity of colouring problems on dense graphs
- Randomized rounding: A technique for provably good algorithms and algorithmic proofs
- Probabilistic construction of deterministic algorithms: approximating packing integer programs
- Bin packing can be solved within 1+epsilon in linear time
- Optimization, approximation, and complexity classes
- On the greedy algorithm for satisfiability
- Hamiltonian circuits in random graphs
- Randomness in interactive proofs
- Traffic-light scheduling on the grid
- The Metropolis algorithm for graph bisection
- Approximating the Permanent
- Monte-Carlo approximation algorithms for enumeration problems
- Probabilistic checking of proofs
- Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
- Approximate Algorithms for the 0/1 Knapsack Problem
- A Chernoff Bound for Random Walks on Expander Graphs
- A random polynomial-time algorithm for approximating the volume of convex bodies
- The Complexity of Multiterminal Cuts
- On the Approximation of Maximum Satisfiability
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Polynomial time randomized approximation schemes for Tutte–Gröthendieck invariants: The dense case
- MAX-CUT has a randomized approximation scheme in dense graphs
- On the hardness of approximating minimization problems
- Probability Inequalities for Sums of Bounded Random Variables
