**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**

- 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 *(ek+o(k))*-approximation algorithm for *k*-column
sparse PIPs, improving over previously known *O(k^2)**submodular* functions over * (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.

**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)

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)

Abstract:

**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.