Předchozí program semináře, letní semestr 2008 [Previous program, Spring 2008]
19. 5. 2008 (pondělí [Monday], 12:20, MFF UK Malá Strana, posluchárna S10)
Chandra Chekuri, Sanjeev Khanna: Algorithms for 2-Route Cut Problems. ICALP 2008.
Abstract: In this paper we study approximation algorithms for multiroute cut problems in undirected graphs. In these problems the goal is to find a minimum cost set of edges to be removed from a given graph such that the edge-connectivity (or node-connectivity) between certain pairs of nodes is reduced below a given threshold K. In the usual cut problems the edge connectivity is required to be reduced below 1 (i.e. disconnected). We consider the case of K = 2 and obtain poly-logarithmic approximation algorithms for fundamental cut problems including singlesource, multiway-cut, multicut, and sparsest cut. These cut problems are dual to multi-route flows that are of interest in fault-tolerant networks flows. Our results show that the flow-cut gap between 2-route cuts and 2-route flows is poly-logarithmic in undirected graphs with arbitrary capacities. 2-route cuts are also closely related to well-studied feedback problems and we obtain results on some new variants. Multi-route cuts pose interesting algorithmic challenges. The new techniques developed here are of independent technical interest, and may have applications to other cut and partitioning problems.
(referuje Petr Kolman)
12. 5. 2008 (pondělí [Monday], 12:20, MFF UK Malá Strana, posluchárna S10)
Maren Martens, Fernanda Salazar, and Martin Skutella:
Abstract: In the single source unsplittable flow problem, commodities must be routed simultaneously from a common source vertex to certain destination vertices in a given digraph. The demand of each commodity must be routed along a single path. In a groundbreaking paper Dinitz, Garg, and Goemans [4] prove that any given (splittable) flow satisfying certain demands can be turned into an unsplittable flow with the following nice property: In the unsplittable flow, the flow value on any arc exceeds the flow value on that arc in the given flow by no more than the maximum demand. Goemans conjectures that this result even holds in the more general context with arbitrary costs on the arcs when it is required that the cost of the unsplittable flow must not exceed the cost of the given (splittable) flow. The following is an equivalent formulation of Goemans’ conjecture: Any (splittable) flow can be written as a convex combination of unsplittable flows such that the unsplittable flows have the nice property mentioned above. We prove a slightly weaker version of this conjecture where each individual unsplittable flow occurring in the convex combination does not necessarily fulfill the original demands but rounded demands. Preliminary computational results based on our underlying algorithm support the strong version of the conjecture.
Representing Single Source Multicommodity Flows as Convex Combinations of Unsplittable Flows. ESA 2008
(referuje Tomáš Ebenlendr)
28. 4., 5. 5. 2008 (pondělí [Monday], 12:20, MFF UK Malá Strana, posluchárna S10)
Nikhil Bansal, Niv Buchbinder and Joseph (Seffi) Naor:
Abstract: The generalized caching problem is a generalization of the classic paging problem where pages can arbitrary sizes and arbitrary weights. We give the first polylogarithmic competitive algorithm for the problem. Our algorithm is O(log^2 k) competitive. The algorithm is again based on the primal dual framework for online algorithms, but we need several new technical ideas. Especially, we need to work with a substantially stronger LP formulation where exponentially many constraints are added at each time step.
Randomized Competitive Algorithms for Generalized Caching. STOC 2008.
(referuje Jiří Sgall)
14. 4., 21. 4. 2008 (pondělí [Monday], 12:20, MFF UK Malá Strana, posluchárna S10)
Niv Buchbinder, Joseph (Seffi) Naor: Online Primal-Dual Algorithms for Covering and Packing Problems, ESA 2005
(referuje Jiří Sgall)Abstract: We study a wide range of online covering and packing optimization problems. In an online covering problem a linear cost function is known in advance, but the linear constraints that define the feasible solution space are given one by one in an online fashion. In an online packing problem the profit function as well as the exact packing constraints are not fully known in advance. In each round additional information about the profit function and the constraints is revealed. We provide general deterministic primal-dual schemes for online fractional covering and packing problems. We also provide deterministic algorithms for several integral online covering and packing problems. Our scheme is designed via a novel primal-dual technique that extends the scheme used for many offline optimization problems. Recently, it was shown that this general primal-dual framework is useful for capturing many more online problems. We list several of the later results that follow from this approach.
31. 3., 7. 4. 2008 (pondělí [Monday], 12:20, MFF UK Malá Strana, posluchárna S10)
Michel X. Goemans: Minimum Bounded Degree Spanning Trees. FOCS'06.
Abstract: We consider the minimum cost spanning tree problem under the restriction that all degrees must be at most a given value k. We show that we can efficiently find a spanning tree of maximum degree at most k +2 whose cost is at most the cost of the optimum spanning tree of maximum degree at most k. This is almost best possible. The approach uses a sequence of simple algebraic, polyhedral and combinatorial arguments. It illustrates many techniques and ideas in combinatorial optimization as it involves polyhedral characterizations, uncrossing, matroid intersection, and graph orientations (or packing of spanning trees). The result generalizes to the setting where every vertex has both upper and lower bounds and gives then a spanning tree which violates the bounds by at most two units and whose cost is at most the cost of the optimum tree. It also gives a better understanding of the subtour relaxation for both the symmetric and asymmetric traveling salesman problems. The generalization to l-edge-connected subgraphs is briefly discussed.
(referuje Martin Pergel)
17. 3., 14. 4. 2008 (pondělí [Monday], 12:20, MFF UK Malá Strana, posluchárna S10)
Niv Buchbinder, Joseph (Seffi) Naor: Online Primal-Dual Algorithms for Covering and Packing Problems, ESA 2005
(referuje Jiří Sgall)Abstract: We study a wide range of online covering and packing optimization problems. In an online covering problem a linear cost function is known in advance, but the linear constraints that define the feasible solution space are given one by one in an online fashion. In an online packing problem the profit function as well as the exact packing constraints are not fully known in advance. In each round additional information about the profit function and the constraints is revealed. We provide general deterministic primal-dual schemes for online fractional covering and packing problems. We also provide deterministic algorithms for several integral online covering and packing problems. Our scheme is designed via a novel primal-dual technique that extends the scheme used for many offline optimization problems. Recently, it was shown that this general primal-dual framework is useful for capturing many more online problems. We list several of the later results that follow from this approach.
10. 3., 17. 3. 2008 (pondělí [Monday], 12:20, MFF UK Malá Strana, posluchárna S10)
Marek Chrobak, Christoph Durr, Mathilde Hurand, and Julien Robert:
Algorithms for Temperature-Aware Task Scheduling in Microprocessor Systems
(referuje Ondřej Zajíček)
Abstract: We study scheduling problems motivated by recently developed techniques for microprocessor thermal management at the operating systems level. The general scenario can be described as follows. The microprocessor's temperature is controlled by the hardware thermal management system that continuously monitors the chip temperature and automatically reduces the processor's speed as soon as the thermal threshold is exceeded. Some tasks are more CPU-intensive than other and thus generate more heat during execution. The cooling system operates non-stop, reducing (at an exponential rate) the deviation of the processor's temperature from the ambient temperature. As a result, the processor's temperature, and thus the performance as well, depends on the order of the task execution. Given a variety of possible underlying architectures, models for cooling and for hardware thermal management, as well as types of tasks, this scenario gives rise to a plethora of interesting and never studied scheduling problems.
We focus on scheduling real-time jobs in a simplified model for cooling and thermal management. A collection of unit-length jobs is given, each job speci ed by its release time, deadline and heat contribution. If, at some time step, the temperature of the system is and the processor executes a job with heat contribution h, then the temperature at the next step is ( \tau+h)=2. The temperature cannot exceed the given thermal threshold T. The objective is to maximize the throughput, that is, the number of tasks that meet their deadlines. We prove that, in the on-line case, computing the optimum schedule is NP-hard, even if all jobs are released at the same time. In the online case, we show a 2-competitive deterministic algorithm and a matching lower bound.3. 3. 2008 (pondělí [Monday], 15:40, MFF UK Malá Strana, posluchárna S1)
Uwe Schwiegelshohn, Andrei Tchernykh, Ramin Yahyapour: Online Scheduling in Grids
(referuje Tomáš Ebenlendr)
Abstract: This paper addresses nonclairvoyant and nonpreemptive online job scheduling in Grids. In the applied basic model, the Grid system consists of a large number of identical processors that are divided into several machines. Jobs are independent, they have a fixed degree of parallelism, and they are submitted over time. Further, a job can only be executed on the processors belonging to the same machine. It is our goal to minimize the total makespan. We show that the performance of Garey and Graham’s list scheduling algorithm is significantly worse in Grids than in multiprocessors. Then we present a Grid scheduling algorithm that guarantees a competitive factor of 5. This algorithm can be implemented using a “job stealing” approach and may be well suited to serve as a starting point for Grid scheduling algorithms in real systems.
25. 2. 2008 (pondělí [Monday]], 15:40, MFF UK Malá Strana, posluchárna S1)
Petr Kolman: Hledani cesty bez zakázaných dvojic (On path avoiding fobidden pairs)
Abstract: Given a graph $G=(V,E)$, two fixed vertices $s,t\in V$ and a set $F$ of pairs of vertices (called {\em forbidden pairs}), the {\em problem of a path avoiding forbidden pairs} is to find a path from $s$ to $t$ that contains at most one vertex from each pair in $F$. The problem is known to be NP-complete in general and a few restricted versions of the problem are known to be in P. We study the complexity of the problem with respect to the structure of the forbidden pairs.