scientific article; zbMATH DE number 2086914

zbMath1049.90535MaRDI QIDQ4737518

Dror Livnat, Michael Lewin, Uri Zwick

Publication date: 11 August 2004

Full work available at URL: http://link.springer.de/link/service/series/0558/bibs/2337/23370067.htm

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

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59)

Related Items (31)

On regularity of Max-CSPs and Min-CSPs ⋮ From the quantum approximate optimization algorithm to a quantum alternating operator ansatz ⋮ Complexity issues in color-preserving graph embeddings ⋮ Complexity of approximating CSP with balance/hard constraints ⋮ Maximal and Maximum Transitive Relation Contained in a Given Binary Relation ⋮ Minimum 2SAT-DELETION: Inapproximability results and relations to minimum vertex cover ⋮ Constrained Assortment Optimization Under the Paired Combinatorial Logit Model ⋮ On the approximability of digraph ordering ⋮ A new upper bound for Max-2-SAT: A graph-theoretic approach ⋮ Unnamed Item ⋮ Technical Note—Assortment Optimization with Small Consideration Sets ⋮ Approximation Algorithms for CSPs ⋮ Global Cardinality Constraints Make Approximating Some Max-2-CSPs Harder ⋮ Simultaneous approximation of multi-criteria submodular function maximization ⋮ Sums of squares based approximation algorithms for MAX-SAT ⋮ Simple approximation algorithms for balanced MAX~2SAT ⋮ Optimal Allocation in Combinatorial Auctions with Quadratic Utility Functions ⋮ Approximation algorithms from inexact solutions to semidefinite programming relaxations of combinatorial optimization problems ⋮ A New Upper Bound for Max-2-SAT: A Graph-Theoretic Approach ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A spectral partitioning algorithm for maximum directed cut problem ⋮ A new bounding procedure and an improved exact algorithm for the Max-2-SAT problem ⋮ Online Submodular Maximization with Preemption ⋮ Random MAX SAT, random MAX CUT, and their phase transitions ⋮ Unnamed Item ⋮ Semidefinite programming based approaches to the break minimization problem ⋮ Hardness of approximation for knapsack problems ⋮ Oblivious algorithms for the maximum directed cut problem ⋮ Greedy Algorithms for the Maximum Satisfiability Problem: Simple Algorithms and Inapproximability Bounds ⋮ Improved approximation for orienting mixed graphs

This page was built for publication: