Find link

language:

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

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

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

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,788 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,282 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