Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
type: Item
instance of: scholarly article
title: Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
zbMATH Open document ID: 0937.68160
author: Marek Karpinski
author: David R. Karger
author: Sanjeev Arora
published in: Journal of Computer and System Sciences
publication date: 2000-02-17T00:00:00Z
Mathematics Subject Classification ID: 68W10
zbMATH DE Number: 1343338
zbMATH Keywords: polynomial time approximation schemes
zbMATH Keywords: exhaustive sampling
Wikidata QID: Q56387952
MaRDI profile type: Publication
full work available at URL: jcss.1998.1605
OpenAlex ID: W2065641139
cites work: Polynomial time randomized approximation schemes for Tutte–Gröthendieck invariants: The dense case
cites work: Q4230322
cites work: Probabilistic checking of proofs
cites work: Randomness in interactive proofs
cites work: A random polynomial-time algorithm for approximating the volume of convex bodies
cites work: The Complexity of Multiterminal Cuts
cites work: The complexity of colouring problems on dense graphs
cites work: MAX-CUT has a randomized approximation scheme in dense graphs
cites work: Bin packing can be solved within 1+epsilon in linear time
cites work: A Chernoff Bound for Random Walks on Expander Graphs
cites work: Q4198056
cites work: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
cites work: Q4526964
cites work: Probability Inequalities for Sums of Bounded Random Variables
cites work: Q4864428
cites work: Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
cites work: Approximating the Permanent
cites work: The Metropolis algorithm for graph bisection
cites work: A new polynomial-time algorithm for linear programming
cites work: Monte-Carlo approximation algorithms for enumeration problems
cites work: Q4526965
cites work: On the greedy algorithm for satisfiability
cites work: Traffic-light scheduling on the grid
cites work: On the hardness of approximating minimization problems
cites work: Hamiltonian circuits in random graphs
cites work: Q3221403
cites work: Optimization, approximation, and complexity classes
cites work: Probabilistic construction of deterministic algorithms: approximating packing integer programs
cites work: Randomized rounding: A technique for provably good algorithms and algorithmic proofs
cites work: Approximate Algorithms for the 0/1 Knapsack Problem
cites work: Q4840777
cites work: On the Approximation of Maximum Satisfiability
DOI: 10.1006/JCSS.1998.1605
Recommended article: Q4234075
Recommended article: Polynomial time approximation schemes for some dense instances of NP-hard optimization problems
Recommended article: Q4638059
Recommended article: Polynomial time approximation schemes and parameterized complexity
Recommended article: Mathematical Foundations of Computer Science 2004
Recommended article: Polynomial time approximation schemes for dense instances of minimum constraint satisfaction
Recommended article: Q4782694
Recommended article: On the efficiency of polynomial time approximation schemes
Recommended article: Approximation algorithms for NP-hard problems
Recommended article: Q4792058
description: scientific article; zbMATH DE number 1343338