Seminář z aproximačních a online algoritmů

Petr Kolman, Jiří Sgall

Předchozí program semináře, zimní semestr 2006 [Previous program, Fall 2006]

9. 1. 2007 (úterý [Tuesday], 9:00, MFF UK Malá Strana S9)

Sanjeev Arora, Eden Chlamtac, Moses Charikar: New approximation guarantee for chromatic number. STOC'06.
(referuje Jan Kadlec)

Abstract: We describe how to color every 3-colorable graph with O(n^0.2111) colors, thus improving an algorithm of Blum and Karger from almost a decade ago. Our analysis uses new geometric ideas inspired by the recent work of Arora, Rao, and Vazirani on SPARSEST CUT, and these ideas show promise of leading to further improvements.

19. 12. 2006 (úterý [Tuesday], 9:00, MFF UK Malá Strana S9)

Brian C. Dean, Michel X. Goemans, Nicole Immorlica:
Finite Termination of "Augmenting Path" Algorithms in the Presence of Irrational Problem Data. ESA'06.
(referuje Tomáš Ebenlendr)

Abstract: This paper considers two similar graph algorithms that work by repeatedly increasing “flow” along “augmenting paths”: the Ford-Fulkerson algorithm for the maximum flow problem and the Gale-Shapley algorithm for the stable allocation problem (a many-to-many generalization of the stable matching problem). Both algorithms clearly terminate when given integral input data. For real-valued input data, it was previously known that the Ford-Fulkerson algorithm runs in polynomial time if augmenting paths are chosen via breadth-first search, but that the algorithm might fail to terminate if augmenting paths are chosen in an arbitrary fashion. However, the performance of the Gale-Shapley algorithm on real-valued data was unresolved. Our main result shows that, in contrast to the Ford-Fulkerson algorithm, the Gale-Shapley algorithm always terminates in finite time on real-valued data. Although the Gale-Shapley algorithm may take exponential time in the worst case, it is a popular algorithm in practice due to its simplicity and the fact that it often runs very quickly (even in sublinear time) for many inputs encountered in practice. We also study the Ford-Fulkerson algorithm when augmenting paths are chosen via depth-first search, a common implementation in practice. We prove that, like breadth-first search, depth-first search also leads to finite termination (although not necessarily in polynomial time).

5. 12., 12. 12. 2006 (úterý [Tuesday], 9:00, MFF UK Malá Strana S9)

Lisa Fleischer: Fast Approximation Algorithms for Fractional Covering Problems with Box Constraints. SODA'04.
(referuje Pavel Nejedlý)

Abstract: We present the first combinatorial approximation scheme that yields a pure approximation guarantee for linear programs that are either covering problems with upper bounds on variables, or their duals. Existing approximation schemes for mixed covering and packing problems do not simultaneously satisfy packing and covering constraints exactly. We present the first combinatorial approximation scheme that returns solutions that simultaneously satisfy general positive covering constraints and upper bounds on variable values. For input parameter eps>0, the returned solution has positive linear objective function value at most 1+eps times the optimal value. The general algorithm requires O(eps^2 m log(c^T u)) iterations, where c is the objective cost vector, u is the vector of upper bound values, and m is the number of variables. Each iteration uses an oracle that. Finds an (approximately) most violated constraint.

A natural set of problems that our work addresses are linear programs for various network design problems: generalized Steiner network, vertex connectivity, directed connectivity, capacitated network design, group Steiner forest. The integer versions of these problems are all NP-hard. For each of them, there is an approximation algorithm that rounds the solution to the corresponding linear program relaxation. If the LP solution is not feasible, then the corresponding integer solution will also not be feasible. Solving the linear program is often the computational bottleneck in these problems, and thus a fast approximation scheme for the LP relaxation means faster approximation algorithms.

21. 11., 28. 11. 2006 (úterý [Tuesday], 9:00, MFF UK Malá Strana S9)

Jonathan A. Kelner, Daniel A. Spielman: A Randomized Polynomial-Time Simplex Algorithm for Linear Programming. STOC'06. předběžná verze ECCC TR05-156
(referuje Marek Krčál)

Abstract: We present the first randomized polynomial-time simplex algorithm for linear programming. Like the other known polynomial-time algorithms for linear programming, its running time depends polynomially on the number of bits used to represent its input. We begin by reducing the input linear program to a special form in which we merely need to certify boundedness. As boundedness does not depend upon the right-hand-side vector, we run the shadow-vertex simplex method with a random right-hand-side vector. Thus, we do not need to bound the diameter of the original polytope. Our analysis rests on a geometric statement of independent interest: given a polytope $A x leq b$ in isotropic position, if one makes a polynomially small perturbation to $b$ then the number of edges of the projection of the perturbed polytope onto a random 2-dimensional subspace is expected to be polynomial.

7. 11., 14. 11. 2006 (úterý [Tuesday], 9:00, MFF UK Malá Strana S9)

Jeff Edmonds and Kirk Pruhs: Balanced Allocations of Cake.
(referuje Ondřej Zajíček)

Abstract: We give a randomized algorithm for the well known caking cutting problem that achieves approximate fairness, and has complexity O(n). The heart of this this result involves extending the standard offline multiplechoice balls and bins analysis to the case where the underlying resources/bins/machines have different utilities to different players/balls/jobs.

24. 10., 31. 10. 2006 (úterý [Tuesday], 9:00, MFF UK Malá Strana S9)

Henning Bruhn, Jakub Cerný, Alexander Hall, Petr Kolman:
Single Source Multiroute Flows and Cuts on Uniform Capacity Networks. To appear in SODA'07.
(referuje Petr Kolman)

Abstract: For an integer $h\geq 1$, an elementary $h$-route flow is a flow along $h$ edge disjoint paths between a source and a sink, each path carrying a unit of flow, and a single commodity $h$-route flow is a non-negative linear combination of elementary $h$-route flows. An instance of a single source multicommodity flow problem for a graph $G=(V,E)$ consists of a source vertex $s\in V$ and $k$ sinks $t_1,...,t_k\in V$; we denote it $\CI=(s;t_1,...,t_k)$. In the single source multicommodity multiroute flow problem, we are given an instance $\CI=(s;t_1,...,t_k)$ and an integer $h\geq 1$, and the objective is to maximize the total amount of flow that is transferred from the source to the sinks so that the capacity constraints are obeyed and, moreover, the flow of each commodity is an $h$-route flow.
We study the relation between classical and multiroute single source flows on networks with uniform capacities and we provide a tight bound. In particular, we prove the following result. Given an instance $\CI=(s;t_1,...,t_k)$ such that each $s-t_i$ pair is $h$-connected, the maximum classical flow between $s$ and the $t_i$'s is at most $2(1-1/h)$-times larger than the maximum $h$-route flow between $s$ and the $t_i$'s and this is the best possible bound for $h\geq 2$. This, as we show, is in contrast to the situation of general multicommodity multiroute flows that are up to $k(1-1/h)$-times smaller than their classical counterparts.
As a corollary, we establish a max-flow min-cut theorem for the single source multicommodity multiroute flow and cut. An $h$-disconnecting cut for $\CI$ is a set of edges $F\subseteq E$ such that for each $i$, the maximum $h$-route flow between $s-t_i$ is zero. We show that the maximum $h$-route flow is within $2(h-1)$ of the mininimum $h$-disconnecting cut, independently of the number of commodities; we also describe a $2(h-1)$-approximation algorithm for the minimum $h$-disconnecting cut problem.

10. 10., 17. 10. 2006 (úterý [Tuesday], 9:00, MFF UK Malá Strana S9)

M. Chrobak, W. Jawor, J. Sgall, T. Tichy:
Online scheduling of equal-length jobs: Randomization and restarts help. To appear in SIAM J. Comput.
(referuje Jiří Sgall)

Abstract: We consider the following scheduling problem. The input is a set of jobs with equal processing times, where each job is specified by its release time and deadline. The goal is to determine a single-processor, non-preemptive schedule that maximizes the number of completed jobs. In the online version, each job arrives at its release time. We give two online algorithms with competitive ratios below $2$ and show several lower bounds on the competitive ratios. First, we give a barely random $5/3$-competitive algorithm that uses only one random bit. Second, we give a deterministic $3/2$-competitive algorithm in the model that allows restarts.