Gadgets, Approximation, and Linear Programming

DOI10.1137/S0097539797328847zbMATH Open0957.68048OpenAlexW2146489710MaRDI QIDQ4507337FDOQ4507337

Authors: Luca Trevisan, Gregory B. Sorkin, David P. Williamson, Madhu Sudan 

Publication date: 18 October 2000

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539797328847

Recommendations

• .878-approximation algorithms for MAX CUT and MAX 2SAT
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
• scientific article; zbMATH DE number 1559516
• scientific article; zbMATH DE number 6823767

zbMATH Keywords

combinatorial optimizationapproximation algorithmsNP-completenessreductionsintractabilityprobabilistic proof systems

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cited In (45)

• Title not available (Why is that?)
• Some recent strong inapproximability results
• Fast Distributed Approximation for Max-Cut
• Chromatic kernel and its applications
• Improved NP-inapproximability for 2-variable linear equations
• A manifesto for the computational method
• Short PCPPs verifiable in polylogarithmic time with \(O(1)\) queries
• Facets from gadgets
• Constrained submodular maximization via a nonsymmetric technique
• Complexity of maximum cut on interval graphs
• New NP-hardness results for 3-coloring and 2-to-1 label cover
• Pseudo-Boolean optimization
• On the complexity of binary polynomial optimization over acyclic hypergraphs
• Bisections of graphs
• A tight linear time (1/2)-approximation for unconstrained submodular maximization
• On Khot’s unique games conjecture
• On the hardness of efficiently approximating maximal non-\(L\) submatrices.
• An algorithmic regularity lemma for \(L_p\) regular sparse matrices
• Streaming submodular maximization with the chance constraint
• Differential approximation of MIN SAT, MAX SAT and related problems
• Approximation algorithms from inexact solutions to semidefinite programming relaxations of combinatorial optimization problems
• Max-Cut via Kuramoto-Type Oscillators
• Improved approximations for max set splitting and max NAE SAT
• Randomized Competitive Analysis for Two-Server Problems
• Max-bisections of \(H\)-free graphs
• Complexity classification of some edge modification problems
• Finding an unknown acyclic orientation of a given graph
• The complexity of Boolean constraint satisfaction local search problems
• Approximation algorithms for balancing signed graphs
• On the configuration LP for maximum budgeted allocation
• Linear-programming design and analysis of fast algorithms for Max 2-CSP
• A nonmonotone GRASP
• Positive linear programming, parallel approximation and PCP's
• Combining clustered adaptive multistart and discrete dynamic convexized method for the max-cut problem
• Non-approximability of weighted multiple sequence alignment.
• A fast algorithm for maximizing a non-monotone DR-submodular integer lattice function
• Approximating CSPs with global cardinality constraints using SDP hierarchies
• Large cuts with local algorithms on triangle-free graphs
• Randomized competitive analysis for two server problems
• Efficient minimization of higher order submodular functions using monotonic Boolean functions
• Judicious partitions of directed graphs
• Online submodular maximization with preemption
• Reductions, completeness and the hardness of approximability
• Adapting local sequential algorithms to the distributed setting
• On weighted vs unweighted versions of combinatorial optimization problems

This page was built for publication: Gadgets, Approximation, and Linear Programming

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4507337)