Solving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximations

DOI10.1016/S0377-2217(02)00071-1zbMath1001.90050MaRDI QIDQ1598763

Dorit S. Hochbaum

Publication date: 28 May 2002

Published in: European Journal of Operational Research (Search for Journal in Brave)

zbMATH Keywords

approximation algorithmminimum cutvertex covermaximum cliqueminimum satisfiabilityhalf integralitysuperoptimalfeasible cutgeneralized satisfiability

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Integer programming (90C10) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08)

Related Items (23)

Approximation algorithms for submodular vertex cover problems with linear/submodular penalties using primal-dual technique ⋮ Complexity and Polynomially Solvable Special Cases of QUBO ⋮ A packet filter placement problem with application to defense against spoofed denial of service attacks ⋮ Deterministic versus randomized adaptive test cover ⋮ HNCcorr: combinatorial optimization for neuron identification ⋮ Classes of linear programs solvable by coordinate-wise minimization ⋮ Randomized Adaptive Test Cover ⋮ Data Reduction for Maximum Matching on Real-World Graphs ⋮ Applications and efficient algorithms for integer programming problems on monotone constraints ⋮ Generalized roof duality and bisubmodular functions ⋮ Monotonizing linear programs with up to two nonzeroes per column ⋮ Optimization with binet matrices ⋮ Relaxation Analysis for the Dynamic Knapsack Problem with Stochastic Item Sizes ⋮ A comparative study of the leading machine learning techniques and two new optimization algorithms ⋮ L-extendable functions and a proximity scaling algorithm for minimum cost multiflow problem ⋮ The generalized vertex cover problem and some variations ⋮ Min sum clustering with penalties ⋮ Complexity and approximations for submodular minimization problems on two variables per inequality constraints ⋮ Half-integrality, LP-branching, and FPT Algorithms ⋮ A simple rounding scheme for multistage optimization ⋮ Algorithms for the generalized independent set problem based on a quadratic optimization approach ⋮ Decreasing minimization on M-convex sets: background and structures ⋮ LP-based algorithms for multistage minimization problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Primal-dual approximation algorithms for integral flow and multicut in trees
• Efficient bounds for the stable set, vertex cover and set packing problems
• Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality
• On approximation algorithms for the minimum satisfiability problem
• Approximating a generalization of MAX 2SAT and MIN 2SAT
• A cut-based algorithm for the nonlinear dual of the minimum cost network flow problem
• An approximate max-flow min-cut relation for undirected multicommodity flow, with applications
• A half-integral linear programming relaxation for scheduling precedence-constrained jobs on a single machine
• A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
• Finding Minimum-Cost Circulations by Successive Approximation
• Combinatorial Algorithms for the Generalized Circulation Problem
• The maximum concurrent flow problem
• The Computational Complexity of Simultaneous Diophantine Approximation Problems
• A new approach to the maximum-flow problem
• Edge-Deletion Problems
• Approximation Algorithms for the Set Covering and Vertex Cover Problems
• Maximal Closure of a Graph and Applications to Combinatorial Problems
• Approximating Clique and Biclique Problems
• The Minimum Satisfiability Problem
• Lower and Upper Bounds for the Allocation Problem and Other Nonlinear Optimization Problems
• A Faster Algorithm for Finding the Minimum Cut in a Directed Graph
• Simple and Fast Algorithms for Linear and Integer Programs with Two Variables Per Inequality
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Multiway cuts in directed and node weighted graphs
• A Fast Parametric Maximum Flow Algorithm and Applications
• Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
• A Faster Strongly Polynomial Minimum Cost Flow Algorithm
• An efficient algorithm for image segmentation, Markov random fields and related problems
• Some optimal inapproximability results
• Approximation algorithms for feasible cut and multicut problems

This page was built for publication: Solving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximations