Gadgets, Approximation, and Linear Programming
From MaRDI portal
Publication:4507337
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
Cited in
(45)- scientific article; zbMATH DE number 7559092 (Why is no real title available?)
- Some recent strong inapproximability results
- Chromatic kernel and its applications
- Fast Distributed Approximation for Max-Cut
- A manifesto for the computational method
- Improved NP-inapproximability for 2-variable linear equations
- Short PCPPs verifiable in polylogarithmic time with \(O(1)\) queries
- Facets from gadgets
- Constrained submodular maximization via a nonsymmetric technique
- New NP-hardness results for 3-coloring and 2-to-1 label cover
- Complexity of maximum cut on interval graphs
- Pseudo-Boolean optimization
- Bisections of graphs
- A tight linear time (1/2)-approximation for unconstrained submodular maximization
- On the complexity of binary polynomial optimization over acyclic hypergraphs
- 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
- A nonmonotone GRASP
- Linear-programming design and analysis of fast algorithms for Max 2-CSP
- Combining clustered adaptive multistart and discrete dynamic convexized method for the max-cut problem
- Positive linear programming, parallel approximation and PCP's
- Non-approximability of weighted multiple sequence alignment.
- A fast algorithm for maximizing a non-monotone DR-submodular integer lattice function
- Large cuts with local algorithms on triangle-free graphs
- Approximating CSPs with global cardinality constraints using SDP hierarchies
- 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
- On weighted vs unweighted versions of combinatorial optimization problems
- Adapting local sequential algorithms to the distributed setting
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)
