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

Petr Kolman, Jiří Sgall

Předchozí program semináře [Previous program]

23. 5. 2013 (čtvrtek [Thursday], 12:20, MFF UK Malá Strana S1)

Yonatan Bilu, Amit Daniely, Nati Linial and Mike Saks: On the practically interesting instances of MAXCUT. STACS 2013. Also http://arxiv.org/abs/1205.4893
(referuje Dušan Knop)

Abstract. For many optimization problems, the instances of practical interest often occupy just a tiny part of the algorithm's space of instances. Following (Y. Bilu and N. Linial, 2010), we apply this perspective to MAXCUT, viewed as a clustering problem. Using a variety of techniques, we investigate practically interesting instances of this problem. Specifically, we show how to solve in polynomial time distinguished, metric, expanding and dense instances of MAXCUT under mild stability assumptions. In particular, (1 + epsilon)-stability (which is optimal) suffices for metric and dense MAXCUT. We also show how to solve in polynomial time Omega(sqrt(n))-stable instances of MAXCUT, substantially improving the best previously known result.

2. 5. 2013 (čtvrtek [Thursday], 12:20, MFF UK Malá Strana S1)

Martin Koutecký: Solving Hard Problems on Neighborhood Diversity

Abstract. Neighborhood diversity is a recently introduced graph structural parameter which has many interesting qualities in the area of parameterized complexity. A result that proved remarkably useful when working with graphs of bounded neighborhood diversity is the so called Lenstra's algorithm, which solves an integer linear program in fixed dimension in polynomial time. We present an application of this algorithm to several NP-hard problems for graphs of bounded neighborhood diversity. Namely we show that when neighborhood diversity is bounded by some constant, these problems become polynomial time solvable:
- Capacitated Dominating Set
- Achromatic Number
- L(p,q)-labeling (due to Fiala, Gavenčiak, Knop and Kratochvíl, in preparation)
The first two results are due to the author and are presented in his Master's thesis.

25. 4. 2013 (čtvrtek [Thursday], 12:20, MFF UK Malá Strana S1)

Nikhil Bansal, Nitish Korula, Viswanath Nagarajan, and Aravind Srinivasan: Solving Packing Integer Programs via Randomized Rounding with Alterations. Theory of Computing 8:533-565, 2012.
(referuje Martin Böhm)

Abstract. We give new approximation algorithms for packing integer programs (PIPs) by employing the method of randomized rounding combined with alterations. Our first result is a simpler approximation algorithm for general PIPs which matches the best known bounds, and which admits an efficient parallel implementation. We also extend these results to a multi-criteria version of PIPs. Our second result is for the class of packing integer programs (PIPs) that are column sparse, i.e., where there is a specified upper bound k on the number of constraints that each variable appears in. We give an (ek+o(k))-approximation algorithm for k-column sparse PIPs, improving over previously known O(k^2)-approximation ratios. We also generalize our result to the case of maximizing non-negative monotone submodular functions over k-column sparse packing constraints, and obtain an (e^2k/(e-1)+o(k))-approximation algorithm. In obtaining this result, we prove a new property of submodular functions that generalizes the fractional subadditivity property, which might be of independent interest.

11. 4., 18. 4. 2013 (čtvrtek [Thursday], 12:20, MFF UK Malá Strana S1)

Manisha Bansal, Naveen Garg, and Neelima Gupta: A 5-Approximation for Capacitated Facility Location. ESA 2012.
(referuje Jakub Velkoborský)

Abstract. In this paper, we propose and analyze a local search algorithm for the capacitated facility location problem. Our algorithm is a modification of the algorithm proposed by Zhang et al. and improves the approximation ratio from 5.83 to 5. We achieve this by modifying the close, open and multi operations. The idea of taking linear combinations of inequalities used in Aggarwal et al. is crucial in achieving this result. The example proposed by Zhang et al. also shows that our analysis is tight.

28. 3., 4. 4. 2013 (čtvrtek [Thursday], 12:20, MFF UK Malá Strana S1)

Leah Epstein, Asaf Levin, Danny Segev and Oren Weimann: Improved bounds for online preemptive matching. STACS 2013. Also http://arxiv.org/abs/1207.1788
(referuje Pavel Veselý)

Abstract: When designing a preemptive online algorithm for the maximum matching problem, we wish to maintain a valid matching M while edges of the underlying graph are presented one after the other. When presented with an edge e, the algorithm should decide whether to augment the matching M by adding e (in which case e may be removed later on) or to keep M in its current form without adding e (in which case e is lost for good). The objective is to eventually hold a matching M with maximum weight.
The main contribution of this paper is to establish new lower and upper bounds on the competitive ratio achievable by preemptive online algorithms:
1. We provide a lower bound of 1+ln 2~1.693 on the competitive ratio of any randomized algorithm for the maximum cardinality matching problem, thus improving on the currently best known bound of e/(e-1)~1.581 due to Karp, Vazirani, and Vazirani [STOC'90].
2. We devise a randomized algorithm that achieves an expected competitive ratio of 5.356 for maximum weight matching. This finding demonstrates the power of randomization in this context, showing how to beat the tight bound of 3 +2\sqrt{2}~5.828 for deterministic algorithms, obtained by combining the 5.828 upper bound of McGregor [APPROX'05] and the recent 5.828 lower bound of Varadaraja [ICALP'11].

21. 3. 2013 (čtvrtek [Thursday], 12:20, MFF UK Malá Strana S1)

Z. Nutov: Approximating minimum-cost connectivity problems via uncrossable bifamilies. ACM Trans. Alg. 9(1), Article no. 1, 2012.
(referuje Tomáš Masařík)

Abstract: We give approximation algorithms for the Survivable Network problem. The input consists of a graph G = (V, E) with edge/node-costs, a node subset S ⊆ V, and connectivity requirements {r(s, t) : s, t ∈ T ⊆ V}. The goal is to find a minimum cost subgraph H of G that for all s, t ∈T contains r(s, t) pairwise edge-disjoint st-paths such that no two of them have a node in S \ {s, t} in common. Three extensively studied particular cases are: Edge-Connectivity Survivable Network (S = ∅), Node-Connectivity Survivable Network (S = V), and Element-Connectivity Survivable Network (r(s, t) = 0 whenever s ∈ S or t ∈ S). Let k = max_{s,t∈T} r(s, t). In Rooted Survivable Network, there is s ∈ T such that r(u, t) = 0 for all u != s, and in the Subset k-Connected Subgraph problem r(s, t) = k for all s, t ∈ T.
For edge-costs, our ratios are O(klog k) for Rooted Survivable Network and O(k2 log k) for Subset k-Connected Subgraph. This improves the previous ratio O(k2 log n), and for constant values of k settles the approximability of these problems to a constant.
For node-costs, our ratios are as follows.
—O(klog |T|) for Element-Connectivity Survivable Network, matching the best known ratio for Edge-
Connectivity Survivable Network.
—O(k2 log |T|) for Rooted Survivable Network and O(k3 log |T|) for Subset k-Connected Subgraph, improving
the ratio O(k8 log2 |T|).
—O(k4 log2 |T|) for Survivable Network; this is the first nontrivial approximation algorithm for the node-costs
version of the problem.

7. 3. 2013 (čtvrtek [Thursday], 12:20, MFF UK Malá Strana S1)

Dušan Knop: Parametrizovana slozitost delkou omezenych rezu a multi-rezu

Abstract: Predvedu dukaz, ze minimalni delkou omezeny rez je mozne najit FPT algoritmem v case f(L,t)n, kde L je parametr delky cest a t je stromova sirka grafu ve kterem rez hledame a f() je spocitatelna funkce. Pokud nam vyjde cas, tak predvedu i dusledky (napr. algoritmus pro vicekomoditni omezene rezy).

28. 2. 2013 (čtvrtek [Thursday], 12:20, MFF UK Malá Strana S1)

Petr Kolman: L-omezene rezy a nova linearni relaxace

Abstract: V problemu L-omezeneho rezu je dan graf G, dva jeho vrcholy s a t (nazyvane zdroj a stok) a celociselny parametr L. Ukolem je najit podmnozinu hran minimalni (co do poctu) velikosti takovou, ze po jejim odstraneni ma kazda cesta mezi s a t uz delku vetsi nez L. Jedna se o NP-tezky problem, ktery se zatim umi jen velmi spatne aproximovat. V seminari nastinim slabosti linearni relaxace, o ktere jsme se bavili pred rokem (neocekavam, ze si nekdo neco pamatuje), a predstavim relaxaci jinou a s ni souvisejici otevrene problemy.

21. 2. 2013 (čtvrtek [Thursday], 12:20, MFF UK Malá Strana S1)

Jiří Sgall: Multiprocessor jobs, preemptive schedules, and one-competitive online algorithms
(joint work with Gerhard J. Woeginger)

Abstract: We investigate online preemptive scheduling of parallel jobs with release times on m parallel machines. The jobs arrive over time, the length (the processing time) and the width (the number of machines needed) of each job are known at the release time of that job. Our goal is to construct a preemptive schedule with the minimal length of schedule (makespan). We study the case where the set of possible widths of jobs is known and fixed in advance. We characterize all the sets of widths for which it is possible to generate optimal or near-optimal schedules online.