Garg and Könemann PTAS for Max Multicommodity Flow

Posted on November 12, 2011 by Neal

In this note we improve the running time of the PST-style Multicommodity-Flow algorithm from a previous note. We use Garg and Könemann’s idea of non-uniform increments to reduce the worst-case number of iterations to polynomial. This note assumes understanding of that previous note.

Continue reading →

Posted in lagrangian | Tagged , , , , , | Leave a comment

Plotkin et al.-style algorithm for Max Multicommodity Flow

Posted on November 10, 2011 by Neal

In this note we derive two approximation algorithms for Integer Maximum Multicommodity Flow. The algorithms are similar to one we previously mentioned (without a derivation).

The derivations illustrate the basic idea for deriving Lagrangian-relaxation algorithms.

Continue reading →

Posted in lagrangian | Tagged , , , , , , | Leave a comment

Localizing — exercises

Posted on November 3, 2011 by Neal

Here are some exercises related to localizing and the method of alterations.

Continue reading →

Posted in exercises | Tagged , , , , , , , | Leave a comment

Chvatal’s algorithm for Set Cover — alternative (exercise)

Posted on October 29, 2011 by Neal

As illustrated in a previous note, one can use random stopping times and Wald’s equation to control the cost in the derivation of Chvatal’s algorithm.

One can instead use a Markov bound to control the cost, but this leads to a weaker approximation and a more complicated algorithm. The exercises in this note illustrate that.

Continue reading →

Posted in exercises, greedy | Tagged , , , | Leave a comment

Chvátal’s algorithm for Set Cover — approximation ratio

Posted on October 29, 2011 by Neal

This note strengthens the previous proof of the approximation ratio for Chvátal’s algorithm to obtain Chvátal’s original (stronger) bound of , where is the maximum size of any set.

The derivation illustrates the idea of localizing an analysis.

Continue reading →

Posted in greedy | Tagged , , , , | Leave a comment

Chvátal’s algorithm for Set Cover — approximation ratio

Posted on October 29, 2011 by Neal

This note derives Chvátal’s greedy algorithm for Set Cover (with non-uniform set costs), and shows an approximation ratio, where is the number of elements.

This derivation is a good introduction to using a stopping time to control one of the constraints of the desired object (in this case, the coverage).

Continue reading →

Posted in greedy | Tagged , , , , | Leave a comment

Johnson and Lovasz’s algorithm for uniform Set Cover — approximation ratio

Posted on October 29, 2011 by Neal

This note derives Johnson and Lovasz’s greedy algorithm for Set Cover (for the case when all sets have cost 1).

The derivation is a good introduction to the basic idea of deriving greedy (and Lagrangian-relaxation) approximation algorithms via randomized rounding.

Continue reading →

Posted in greedy | Tagged , , , , | Leave a comment

Randomized rounding

Posted on August 9, 2011 by Neal

Randomized rounding, introduced by Raghavan and Thompson in 1987, uses the probabilistic method to round the solution of a linear program to obtain an approximately optimal integer solution [3]. This note describes randomized rounding and gives an example: deriving an approximation algorithm for Set Cover. Continue reading →

Posted in reference | Tagged , | Leave a comment

Stopping times — “all-time” Chernoff bound

Posted on August 6, 2011 by Neal

Standard Chernoff bounds apply to a sum of independent random variables, where the number of variables summed is fixed. If the number of variables summed is itself random, the standard bound does not apply. This note describes a variant for that case.

Continue reading →

Posted in probabilistic method | Tagged , , , , | Leave a comment

Stopping times — introduction and basic bounds

Posted on August 5, 2011 by Neal

How can one analyze random experiments that sample randomly until some condition is met, i.e., experiments with a so-called stopping time?

Continue reading →

Posted in probabilistic method | Tagged , , , , | Leave a comment

The probabilistic method — Chernoff bound

Posted on August 3, 2011 by Neal

Penalty functions with exponential penalty terms are common in Lagrangian relaxation [4]. These penalties are also called multiplicative weights, and algorithms that work with them are also called multiplicative-update algorithms [1].

Exponential functions are used in the probabilistic method in the form of tail bounds (Chernoff/Hoeffding/Azuma/Talagrand inequalities). If we use such bounds to analyze certain kinds of rounding schemes, then apply the method of conditional probabilities, we can get Lagrangian-relaxation algorithms with exponential terms in the penalty function.

Continue reading →

Posted in probabilistic method | Tagged , , , , | Leave a comment

The probabilistic-method — pessimistic estimators

Posted on February 4, 2011 by Neal

Here is another example of the method of conditional probabilities, this time derandomizing the proof of Turán’s theorem.

This example illustrates the use of so-called pessimistic estimators in place of conditional expectations, and how derandomizing a single proof can lead to multiple different algorithms. Continue reading →

Posted in probabilistic method | Tagged , , , , , | Leave a comment

The probabilistic method — method of conditional probabilities

Posted on February 3, 2011 by Neal

The method of conditional probabilities converts probabilistic existence proofs into efficient deterministic algorithms that explicitly construct the desired object. Here is a description of the method, and an example: deriving a greedy 2-approximation for Max-Cut. Continue reading →

Posted in probabilistic method | Tagged , , | Leave a comment

The probabilistic method — reference

Posted on February 2, 2011 by Neal

Here is an introduction to the probabilistic method, a non-constructive method for proving the existence of mathematical structures with desired properties. Continue reading →

Posted in probabilistic method | Tagged , , , | Leave a comment

Linear programming — rounding a relaxation

Posted on February 1, 2011 by Neal

Here is one basic paradigm for approximation algorithms: model the problem as an integer linear program, solve its linear program relaxation, then round the relaxed solution to a solution of the original problem. This note presents two simple examples.

Continue reading →

Posted in linear programming | Tagged , , , , , , | Leave a comment

Linear programming — modeling other problems

Posted on February 1, 2011 by Neal

Modeling a problem as a linear program or integer linear program is a basic skill. Here are two examples.

Continue reading →

Posted in linear programming | Tagged , , , | Leave a comment

Linear programming — reference

Posted on February 1, 2011 by Neal

Here is a brief introduction to Linear Programming and Integer Linear Programming. Continue reading →

Posted in linear programming | Tagged , , , | Leave a comment

Lagrangian-relaxation algorithms — discussion

Posted on February 1, 2010 by Neal

This note briefly discusses Lagrangian-relaxation algorithms and related topics.

Continue reading →

Posted in algorithms, discussion | Tagged , , | Leave a comment

Lagrangian-relaxation algorithm for Multicommodity Flow

Posted on January 31, 2010 by Neal

This note describes a simple Lagrangian-relaxation algorithm, for the Maximum Multicommodity Flow problem. The algorithm illustrates some prototypical aspects of Lagrangian relaxation.

Continue reading →

Posted in algorithms | Tagged , , , | Leave a comment

Greedy algorithm for Set-Cover — Wolsey’s generalization

Posted on January 30, 2010 by Neal

The greedy -approximation algorithm for Set Cover is known to generalize to a class of problems known as minimizing a linear function subject to a submodular constraint. Here is a summary of that result. Continue reading →

Posted in algorithms | Tagged , , , , | Leave a comment