Find link

language:

jump to random article

Find link is a tool written by Edward Betts.

searching for Hardness of approximation 19 found (51 total)

alternate case: hardness of approximation

Minimum relevant variables in linear system (1,053 words) [view diff] no match in snippet view article find links to article

Minimum relevant variables in linear system (Min-RVLS) is a problem in mathematical optimization. Given a linear program, it is required to find a feasible
Madhu Sudan (465 words) [view diff] case mismatch in snippet view article find links to article
is titled Efficient Checking of Polynomials and Proofs and the Hardness of Approximation Problems. He was a research staff member at the IBM Thomas J.
MAX-3SAT (1,450 words) [view diff] exact match in snippet view article find links to article
R, 1/4 clauses are contradicted. This is enough to prove the hardness of approximation ratio 1 − 1 4 ( 1 2 − ϵ ) 1 − ϵ = 7 8 + ϵ ′ {\displaystyle {\frac
Gödel Prize (2,163 words) [view diff] exact match in snippet view article find links to article
Sudan, Madhu; Szegedy, Mario (1998), "Proof verification and the hardness of approximation problems" (PDF), Journal of the ACM, 45 (3): 501–555, CiteSeerX 10
Sanjeev Arora (433 words) [view diff] exact match in snippet view article find links to article
Princeton University Thesis Probabilistic checking of proofs and the hardness of approximation problems. (1994) Doctoral advisor Umesh Vazirani Doctoral students
Set splitting problem (526 words) [view diff] case mismatch in snippet view article find links to article
W.H. Freeman. ISBN 0-7167-1045-5. Petrank, Erez (1994). "The Hardness of Approximation: Gap Location". Computational Complexity. 4 (2). Springer: 133–157
Crown graph (1,137 words) [view diff] exact match in snippet view article find links to article
Fürer (1995) uses crown graphs as part of a construction showing hardness of approximation of coloring problems. Matoušek (1996) uses distances in crown
Boxicity (1,554 words) [view diff] exact match in snippet view article find links to article
of rectangles, and Chlebík & Chlebíková (2005) for results on hardness of approximation of these problems in higher dimensions. Cozzens (1981) shows that
List of University of California, Berkeley alumni (9,848 words) [view diff] exact match in snippet view article find links to article
systems" and 2001 "for the PCP theorem and its applications to hardness of approximation"); RSA Professor of electrical engineering and computer science
Triangle-free graph (2,524 words) [view diff] exact match in snippet view article find links to article
Abboud, Amir; Bringmann, Karl; Khoury, Seri; Zamir, Or (2022), "Hardness of approximation in P via short cycle removal: cycle detection, distance oracles
NP (complexity) (2,784 words) [view diff] exact match in snippet view article
with high probability. This allows several results about the hardness of approximation algorithms to be proven. All problems in P, denoted P ⊆ N P {\displaystyle
Feedback arc set (6,130 words) [view diff] exact match in snippet view article find links to article
approximation ratio better than 1.3606. This is the same threshold for hardness of approximation that is known for vertex cover, and the proof uses the Karp–Lawler
Metric dimension (graph theory) (2,520 words) [view diff] exact match in snippet view article
polynomial time for any ϵ > 0 {\displaystyle \epsilon >0} . The latter hardness of approximation still holds for instances restricted to subcubic graphs, and even
P versus NP problem (7,784 words) [view diff] case mismatch in snippet view article find links to article
; Gasarch, W. "Computational complexity". Aviad Rubinstein's Hardness of Approximation Between P and NP, winner of the ACM's 2017 Doctoral Dissertation
Envy-free pricing (2,559 words) [view diff] no match in snippet view article find links to article
single-minded pricing. Demaine, Feige, Hajiaghayi and Salavatipour show hardness-of-approximation results by reduction from the unique coverage problem. Anshelevich
Nash equilibrium (8,777 words) [view diff] case mismatch in snippet view article find links to article
(1998), A Beautiful Mind, Simon & Schuster. Aviad Rubinstein: "Hardness of Approximation Between P and NP", ACM, ISBN 978-1-947487-23-9 (May 2019), DOI:
No-three-in-line problem (3,842 words) [view diff] exact match in snippet view article find links to article
hard to approximate its size to within a constant factor; this hardness of approximation result is summarized by saying that the problem is APX-hard. If
List of women in mathematics (23,253 words) [view diff] exact match in snippet view article find links to article
Israeli researcher in probabilistically checkable proofs and hardness of approximation Serena Dipierro, Italian expert on partial differential equations
Parameterized approximation algorithm (3,354 words) [view diff] case mismatch in snippet view article find links to article
2-Approximation Algorithm for Treewidth Karthik C. S.: Recent Hardness of Approximation results in Parameterized Complexity Ariel Kulik. Two-variable