Gadgets, Approximation, and Linear Programming
From MaRDI portal
Publication:4507337
DOI10.1137/S0097539797328847zbMath0957.68048OpenAlexW2146489710MaRDI QIDQ4507337
Luca Trevisan, Madhu Sudan, David P. Williamson, Gregory B. Sorkin
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
combinatorial optimizationNP-completenessreductionsapproximation algorithmsintractabilityprobabilistic proof systems
Related Items
Chromatic kernel and its applications, Improved approximations for max set splitting and max NAE SAT, A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization, Some recent strong inapproximability results, Fast Distributed Approximation for Max-Cut, Short PCPPs verifiable in polylogarithmic time with \(O(1)\) queries, Judicious partitions of directed graphs, A nonmonotone GRASP, Randomized competitive analysis for two server problems, Differential approximation of MIN SAT, MAX SAT and related problems, Large cuts with local algorithms on triangle-free graphs, New NP-Hardness Results for 3-Coloring and 2-to-1 Label Cover, On the configuration LP for maximum budgeted allocation, Constrained Submodular Maximization via a Nonsymmetric Technique, Non-approximability of weighted multiple sequence alignment., Linear-programming design and analysis of fast algorithms for Max 2-CSP, Streaming submodular maximization with the chance constraint, Max-Cut via Kuramoto-Type Oscillators, Complexity of maximum cut on interval graphs, On the complexity of binary polynomial optimization over acyclic hypergraphs, A fast algorithm for maximizing a non-monotone DR-submodular integer lattice function, An Algorithmic Regularity Lemma for $L_p$ Regular Sparse Matrices, On the hardness of efficiently approximating maximal non-\(L\) submatrices., Bisections of graphs, Facets from gadgets, Randomized Competitive Analysis for Two-Server Problems, Combining clustered adaptive multistart and discrete dynamic convexized method for the max-cut problem, Finding an Unknown Acyclic Orientation of a Given Graph, Efficient minimization of higher order submodular functions using monotonic Boolean functions, Approximation algorithms from inexact solutions to semidefinite programming relaxations of combinatorial optimization problems, Pseudo-Boolean optimization, Reductions, completeness and the hardness of approximability, The complexity of Boolean constraint satisfaction local search problems, Complexity classification of some edge modification problems, Unnamed Item, Unnamed Item, Max-bisections of \(H\)-free graphs, Approximation algorithms for balancing signed graphs, Strong reductions for extended formulations, Online Submodular Maximization with Preemption, On Khot’s unique games conjecture, Unnamed Item, A manifesto for the computational method
