scientific article; zbMATH DE number 1306875

zbMath0938.68820MaRDI QIDQ4252727

Madhu Sudan, Mihir Bellare, Oded Goldreich

Publication date: 26 April 2000

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

Mathematics Subject Classification ID

Related Items

Annealed replication: A new heuristic for the maximum clique problem, It is hard to know when greedy is good for finding independent sets, Social network coordination and graph routing, Probabilistic proof systems — A survey, Some recent strong inapproximability results, Approximability of maximum splitting of k-sets and some other Apx-complete problems, On approximation algorithms for the minimum satisfiability problem, Extended and discretized formulations for the maximum clique problem, Randomized graph products, chromatic numbers, and the Lovász \(\vartheta\)-function, On comparing algorithms for the maximum clique problem, The complexity of the \(T\)-coloring problem for graphs with small degree, Max NP-completeness made easy, Fortran subroutines for computing approximate solutions of weighted MAX-SAT problems using GRASP, Revisiting alphabet reduction in Dinur’s PCP., Pseudo-Boolean optimization, The computational complexity of some problems of linear algebra, Alphabet indexing for approximating features of symbols, On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems, Some APX-completeness results for cubic graphs, The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative-Type Metrics into ℓ ₁, Extended capabilities for visual cryptography, On the hardness of approximating the minimum consistent acyclic DFA and decision diagram.