Randomized rounding: A technique for provably good algorithms and algorithmic proofs

DOI10.1007/BF02579324zbMath0651.90052WikidataQ29543656 ScholiaQ29543656MaRDI QIDQ1106724

Clark D. Thompson, Prabhakar Raghavan

Publication date: 1987

Published in: Combinatorica (Search for Journal in Brave)

randomized rounding integer linear programs k-matching multicommodity flow problems probabilistic estimations rational relaxations routing in VLSI circuits

Mathematics Subject Classification ID

Integer programming (90C10)

Related Items

Unnamed Item ⋮ Advanced network connectivity features and zonal requirements in covering location problems ⋮ Matheuristics: survey and synthesis ⋮ How Well Can Fine Balance Work for Covariate Balancing ⋮ Configuration balancing for stochastic requests ⋮ Covariance's loss is privacy's gain: computationally efficient, private and accurate synthetic data ⋮ Dynamic unsplittable flows with path-change penalties: new formulations and solution schemes for large instances ⋮ Sparse Semi-Oblivious Routing: Few Random Paths Suffice ⋮ Unnamed Item ⋮ Oblivious Routing for Sensor Network Topologies ⋮ On the parallel approximability of a subclass of quadratic programming. ⋮ Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems ⋮ Optimal oblivious routing in polynomial time ⋮ Constant-time distributed dominating set approximation ⋮ Geometric Aspects of Online Packet Buffering: An Optimal Randomized Algorithm for Two Buffers ⋮ \(\ell_1\)-sparsity approximation bounds for packing integer programs ⋮ Flows with Unit Path Capacities and Related Packing and Covering Problems ⋮ Concentration inequalities for nonlinear matroid intersection ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Minimum Congestion Mapping in a Cloud ⋮ Energy-efficient scheduling and routing via randomized rounding ⋮ Crossing number, pair-crossing number, and expansion ⋮ Single Source Unsplittable Flows with Arc-Wise Lower and Upper Bounds ⋮ Shrinking maxima, decreasing costs: new online packing and covering problems ⋮ Approximate and dynamic rank aggregation ⋮ Comparison of formulations and a heuristic for packing Steiner trees in a graph ⋮ Provable randomized rounding for minimum-similarity diversification ⋮ Cost-efficient scheduling on machines from the cloud ⋮ Randomized metarounding ⋮ Task scheduling in networks ⋮ Weighted fractional and integral \(k\)-matching in hypergraphs ⋮ Scheduling non-preemptible jobs to minimize peak demand ⋮ A fast heuristic algorithm for the maximum concurrent \(k\)-splittable flow problem ⋮ Global wire routing in two-dimensional arrays ⋮ On dependent randomized rounding algorithms ⋮ Efficient algorithms for scheduling parallel jobs with interval constraints in clouds ⋮ On computational capabilities of Ising machines based on nonlinear oscillators ⋮ Computing approximate Nash equilibria in network congestion games ⋮ A derandomized approximation algorithm for the critical node detection problem ⋮ A randomized algorithm with local search for containment of pandemic disease spread ⋮ A matheuristic approach for the quickest multicommodity \(k\)-splittable flow problem ⋮ Configuration of airspace sectors for balancing air traffic controller workload ⋮ Probabilistic construction of deterministic algorithms: approximating packing integer programs ⋮ Tight approximations for resource constrained scheduling and bin packing ⋮ On the rectangle escape problem ⋮ Partial Resampling to Approximate Covering Integer Programs ⋮ Rounding algorithms for covering problems ⋮ A sequential Stackelberg game for dynamic inspection problems ⋮ Approximation algorithms for multiprocessor scheduling under uncertainty ⋮ Distributed approximation of capacitated dominating sets ⋮ An improved algorithm for online machine minimization ⋮ Approximations for generalized unsplittable flow on paths with application to power systems optimization ⋮ Stochastic packing integer programs with few queries ⋮ Geometric rounding: A dependent randomized rounding scheme ⋮ Randomized oblivious integral routing for minimizing power cost ⋮ Computing Approximate Nash Equilibria in Network Congestion Games ⋮ Unnamed Item ⋮ A Preemptive Algorithm for Maximizing Disjoint Paths on Trees ⋮ Approximation Algorithms for Stochastic and Risk-Averse Optimization ⋮ Approximating covering integer programs with multiplicity constraints ⋮ Parallel approximation to high multiplicity scheduling problemsVIAsmooth multi-valued quadratic programming ⋮ The Lower Bound for Koldobsky’s Slicing Inequality via Random Rounding ⋮ Solving the maximum duo-preservation string mapping problem with linear programming ⋮ Step decision rules for multistage stochastic programming: a heuristic approach ⋮ On polynomial complexity of a stochastic algorithm for mixed zero-one programs. ⋮ On complexity, representation and approximation of integral multicommodity flows ⋮ Approximation algorithms for general packing problems and their application to the multicast congestion problem ⋮ Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs ⋮ An exact approach for the maximum concurrent \(k\)-splittable flow problem ⋮ The complexity of controlled selection ⋮ A Lagrange decomposition based branch and bound algorithm for the optimal mapping of cloud virtual machines ⋮ Distributed approximation of \(k\)-service assignment ⋮ Decomposition algorithms for data placement problem based on Lagrangian relaxation and randomized rounding ⋮ On routing in VLSI design and communication networks ⋮ Improved parallel approximation of a class of integer programming problems ⋮ Approximation algorithms ⋮ Randomized approximation of bounded multicovering problems ⋮ Improved randomized approximation algorithms for lot-sizing problems ⋮ Unnamed Item ⋮ A Unified Approach to Mixed-Integer Optimization Problems With Logical Constraints ⋮ The critical node detection problem in networks: a survey ⋮ Multicommodity flow in trees: packing via covering and iterated relaxation ⋮ Approximation algorithms for time-constrained scheduling on line networks ⋮ Geometric and LP-based heuristics for angular travelling salesman problems in the plane ⋮ Pseudo-Boolean optimization ⋮ Approximation algorithms for geometric median problems ⋮ Improved algorithms for latency minimization in wireless networks ⋮ Faster min-max resource sharing in theory and practice ⋮ A preemptive algorithm for maximizing disjoint paths on trees ⋮ The approximability of non-Boolean satisfiability problems and restricted integer programming ⋮ Short length Menger's theorem and reliable optical routing ⋮ Meet and merge: approximation algorithms for confluent flows ⋮ Near-optimal solutions to large-scale facility location problems ⋮ Max-Weight Integral Multicommodity Flow in Spiders and High-Capacity Trees ⋮ Unnamed Item ⋮ New algorithms for maximum disjoint paths based on tree-likeness ⋮ Approximability of the robust representatives selection problem ⋮ Heuristics for the dynamic facility location problem with modular capacities ⋮ An improved derandomized approximation algorithm for the max-controlled set problem ⋮ APPLICATION PLACEMENT ON A CLUSTER OF SERVERS ⋮ Maximum edge-disjoint paths in planar graphs with congestion 2 ⋮ Inapproximability of b-Matching in k-Uniform Hypergraphs ⋮ Packing trees in communication networks ⋮ Routing in Undirected Graphs with Constant Congestion ⋮ New Hardness Results for Routing on Disjoint Paths ⋮ Approximations for the disjoint paths problem in high-diameter planar networks ⋮ Randomized Rounding in the Presence of a Cardinality Constraint ⋮ An Approximation Algorithm for Path Computation and Function Placement in SDNs ⋮ Algorithms as Mechanisms: The Price of Anarchy of Relax and Round ⋮ Flows with unit path capacities and related packing and covering problems ⋮ An approximation algorithm for the maximum spectral subgraph problem ⋮ Unnamed Item ⋮ Approximation algorithms for covering/packing integer programs ⋮ Covering non-uniform hypergraphs ⋮ Unnamed Item ⋮ Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems ⋮ On dependent randomized rounding algorithms ⋮ Off-line admission control for general scheduling problems ⋮ Minimizing maximum fiber requirement in optical networks ⋮ Single source unsplittable flows with arc-wise lower and upper bounds

Cites Work