On dependent randomized rounding algorithms

DOI10.1007/3-540-61310-2_25zbMath1414.90191OpenAlexW1941111399MaRDI QIDQ4645933

Chung-Piaw Teo, Dimitris J. Bertsimas, Rakesh V. Vohra

Publication date: 11 January 2019

Published in: Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-61310-2_25

zbMATH Keywords

satisfiability problemfacility location problempositive edgefractional solutionlotsizing problem

Mathematics Subject Classification ID

Integer programming (90C10) Discrete location and assignment (90B80)

Related Items

Differential approximation of MIN SAT, MAX SAT and related problems, Approximate clustering of incomplete fingerprints

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unimodular functions
• Randomized rounding: A technique for provably good algorithms and algorithmic proofs
• Source sink flows with capacity installation in batches
• Bin packing can be solved within 1+epsilon in linear time
• Minimal cut cover of a graph with an application to the testing of electronic boards
• An approximation algorithm for the generalized assignment problem
• Almost optimal set covers in finite VC-dimension
• On the notion of balance of a signed graph
• .879-approximation algorithms for MAX CUT and MAX 2SAT
• A Greedy Heuristic for the Set-Covering Problem
• Approximation Algorithms for the Set Covering and Vertex Cover Problems
• Exceptional Paper—Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms
• The Minimum Satisfiability Problem
• Nonlinear formulations and improved randomized approximation algorithms for multicut problems
• Shortest paths, single origin‐destination network design, and associated polyhedra