Předchozí program semináře, zimní semestr 2005 [Previous program, Fall 2005]
12. 1. 2006 (čtvrtek [Thursday], 9.00, MFF UK Malá Strana S7)
Wojciech Jawor (UC Riverside, California, USA):
Abstract: We discuss the following online job scheduling problem: n jobs need to be scheduled on m identical machines, without preemption, so that jobs complete in the order of release times and the maximum flow time is minimized. The problem arises in network systems with aggregated links, when it is required that packets complete their arrivals at the destination in the order of their arrivals at the receiver. This requirement is imposed by the IEEE 802.3 (ISO 8002) standard describing link aggregation in Local Area Networks. We present a deterministic algorithm Block with competitive ratio O(\sqrt{n/m}) and show a matching lower bound even for randomized algorithms.
Competitive Analysis of Scheduling Algorithms for Aggregated Links
22. 12. 2005, 5. 1. 2006 (čtvrtek [Thursday], 9.00, MFF UK Malá Strana S7)
Chandra Chekuri, Sanjeev Khanna, and Bruce Shepherd: Edge Disjoint Paths in Planar Graphs. FOCS, 2004.
Chandra Chekuri, Sanjeev Khanna, and Bruce Shepherd: Multicommodity flow, well-linked terminals, and routing problems. STOC, 2005.
(referuje Petr Kučera)Abstract: We study multicommodity routing problems in both edge and node capacitated undirected graphs. The input to each problem is a capacitated graph G = (V, E) and a set T of node pairs. In the simplest setting, the goal is to route a unit of flow for as many pairs as possible subject to the edge (node) capacity constraints. If the flow for a routed pair is required to be along a single path, it is the well-studied disjoint paths problem. The main result of the first paper is a polylogarithmic approximation for MEDP on undirected planar graphs if a congestion of 2 is allowed, that is, we allow up to 2 paths to share an edge. Prior to our work, for any constant congestion, only a polynomial factor approximation was known for planar graphs although much stronger results are known for some special cases such as grids and gridlike graphs. A key idea in these algorithms is to decompose an instance into a collection of instances in which the ter minals are well-linked. Informally speaking, a set of nodes is well-linked in a graph if it does not have small separators. A decomposition into well-linked instances was previously achieved via Racke's hierarchical graph decomposition for oblivious routing [32]. In the second paper, we design a simple new decomposition algorithm that is based on computing sparse cuts in a graph. Our new algorithm improves the earlier results for edge routing problems.
1. 12., 8. 12., 15. 12. 2005 (čtvrtek [Thursday], 9.00, MFF UK Malá Strana S7)
Martin Gairing, Burkhard Monien and Andreas Woclaw.
A Faster Combinatorial Approximation Algorithm for Scheduling Unrelated Parallel Machines. ICALP 2005.
(referuje Tomáš Ebenlendr)
Abstract: We consider the problem of scheduling n independent jobs on m unrelated parallel machines without preemption. Job i takes processing time p_ij on machine j, and the total time used by a machine is the sum of the processing times for the jobs assigned to it. The objective is to minimize makespan. The best known approximation algorithms for this problem compute an optimum fractional solution and then use rounding techniques to get an integral 2-approximation. In this paper we present a combinatorial approximation algorithm that matches this approximation quality. It is much simpler than the previously known algorithms and its running time is better. This is the first time that a combinatorial algorithm always beats the interior point approach for this problem. Our algorithm is a generic minimum cost flow algorithm, without any complex enhancements, tailored to handle unsplittable flow. It pushes unsplittable jobs through a two-layered bipartite generalized network defined by the scheduling problem. In our analysis, we take advantage from addressing the approximation problem directly. In particular, we replace the classical technique of solving the LP-relaxation and rounding afterwards by a completely integral approach. We feel that this approach will be helpful also for other applications.
10. 11, 24. 11. 2005 (čtvrtek [Thursday], 9.00, MFF UK Malá Strana S7)
Jeff Edmonds and Kirk Pruhs: Cake Cutting Really is Not a Piece of Cake. SODA 2006
(referuje Ondřej Zajíček)Abstract: We consider the wellknown cake cutting problem in which a protocol wants to divide a cake among n>=2 players in such a way that each player believes that they got a fair share. The standard Robertson Webb model allows the protocol to make two types of queries, Evaluation and Cut, to the players. A deterministic divideandconquer protocol with complexity O(n log n) is known. Improving on previous lower bounds, we provide an Omega(n log n) lower bound on the complexity of any deterministic protocol, even if the protocol is allowed to assign to a player a piece that is a union of intervals and only guarantee approximate fairness. We accomplish this by lower bounding the complexity to find for a single player, a piece of cake that is both rich in value, and thin in width. We then introduce a version of cake cutting in which the players are able to cut with only finite precision. In this case, we can extend the Omega(n log n) lower bound to include randomized protocols.
27. 10., 3. 11. 2005 (čtvrtek [Thursday], 9.00, MFF UK Malá Strana S7)
J. Kleinberg: An Approximation Algorithm for the Disjoint Paths Problem in Even-Degree Planar Graphs. FOCS 2005
Abstract: In joint work with Eva Tardos in 1995, we asked whether it was possible to obtain a polynomial-time, polylogarithmic approximation algorithm for the disjoint paths problem in the class of all even-degree planar graphs. This paper answers the question in the affirmative, by providing such an algorithm. The algorithm builds on recent work of Chekuri, Khanna, and Shepherd, who considered routing problems in planar graphs where each edge can carry up to two paths.
(referuje Petr Kučera)
20. 10. 2005 (čtvrtek [Thursday], 9.00, MFF UK Malá Strana S7)
Petr Kolman: Edge disjoint paths problem: known results and open problems
Abstract: In the maximum {\em edge disjoint paths} problem (EDP) we are given a (directed or undirected) graph $G=(V,E)$ and a set $T=\{(s_i,t_i): \; 1 \le i \le k\}$ of $k$ requests. The objective is to connect a maximum number of pairs from $T$ along edge disjoint paths. In this talk we will survey known results and mention some prevailing open problems.
13. 10. 2005 (čtvrtek [Thursday], 9.00, MFF UK Malá Strana S5)
Tomáš Ebenlendr, John Noga, Jiří Sgall, Gerhard Woeginger: A note on semi-online machine covering. WAOA 2005.
(referuje Tomáš Ebenlendr)
Abstract: In the machine cover problem we are given $m$ machines and $n$ jobs to be assigned (scheduled) so that the smallest load of a machine is as large as possible. A semi-online algorithm is given in advance the value $\LOPT$ and then the jobs are scheduled one by one as they arrive, without knowledge of the following jobs. We present a deterministic algorithm with competitive ratio $11/6\approx 1.834$ for machine covering with any number of machines and a lower bound showing that no deterministic algorithm can have a competitive ratio below $43/24\approx 1.791$.