Within computer science and operations research,
many combinatorial optimization problems are computationally intractable to solve exactly (to optimality).
Many such problems do admit fast (polynomial time) approximation algorithms—that is, algorithms that are guaranteed to return an approximately optimal solution given any input.
Randomized rounding
is a widely used approach for designing and analyzing such approximation algorithms.
The basic idea is to use the probabilistic method
to convert an optimal solution of a relaxation
of the problem into an approximately optimal solution to the original problem.
The basic approach has three steps:
Formulate the problem to be solved as an integer linear program (ILP).
Compute an optimal fractional solution to the linear programming relaxation (LP) of the ILP.
Round the fractional solution of the LP to an integer solution of the ILP.
(Although the approach is most commonly applied with linear programs,
other kinds of relaxations are sometimes used.
For example, see Goemans' and Williamson's semidefinite programming-based
Max-Cut approximation algorithm.)
The challenge in the first step is to choose a suitable integer linear program.
Familiarity with linear programming, in particular modelling using linear programs and integer linear programs, is required. For many problems, there is a natural integer linear program that works well,
such as in the Set Cover example below. (The integer linear program should have a small
integrality gap;
indeed randomized rounding is often used to prove bounds on integrality gaps.)
In the second step, the optimal fractional solution can typically be computed
in polynomial time
using any standard linear programming algorithm.
In the third step, the fractional solution must be converted into an integer solution
(and thus a solution to the original problem).
This is called rounding the fractional solution.
The resulting integer solution should (provably) have cost
not much larger than the cost of the fractional solution.
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.
The course focuses on mathematical models based on PDEs with random parameters, and presents numerical techniques for forward uncertainty propagation, inverse uncertainty analysis in a Bayesian framew
A randomized algorithm is an algorithm that employs a degree of randomness as part of its logic or procedure. The algorithm typically uses uniformly random bits as an auxiliary input to guide its behavior, in the hope of achieving good performance in the "average case" over all possible choices of random determined by the random bits; thus either the running time, or the output (or both) are random variables.
We revisit the problem max-min degree arborescence, which was introduced by Bateni et al. [STOC'09] as a central special case of the general Santa Claus problem, which constitutes a notorious open question in approximation algorithms. In the former problem ...
This paper addresses the complexity reduction of stochastic homogenization of a class of random materials for a stationary diffusion equation. A cost-efficient approximation of the correctors is obtained using a method designed to exploit quasi-periodicity ...
SIAM PUBLICATIONS2022
, ,
Cutting plane methods are a fundamental approach for solving integer linear programs (ILPs). In each iteration of such methods, additional linear constraints (cuts) are introduced to the constraint set with the aim of excluding the previous fractional opti ...