# Schedule for: 15w5118 - Approximation Algorithms and Parameterized Complexity

Beginning on Sunday, November 29 and ending Friday December 4, 2015

All times in Banff, Alberta time, MST (UTC-7).

Sunday, November 29 | |
---|---|

16:00 - 17:30 | Check-in begins at 16:00 on Sunday and is open 24 hours (Front Desk - Professional Development Centre) |

17:30 - 19:30 |
Dinner ↓ A buffet dinner is served daily between 5:30pm and 7:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building. (Vistas Dining Room) |

20:00 - 22:00 | Informal gathering (Corbett Hall Lounge (CH 2110)) |

Monday, November 30 | |
---|---|

07:00 - 08:45 |
Breakfast ↓ Breakfast is served daily between 7 and 9am in the Vistas Dining Room, the top floor of the Sally Borden Building. (Vistas Dining Room) |

08:45 - 09:00 | Introduction and Welcome by BIRS Station Manager (TCPL 201) |

09:05 - 10:05 |
Mohammad Taghi Hajiaghayi: Fixed-Parameter Tractability and Approximability: A Survey of Connections ↓ In this talk we discuss briefly classes of xed-parameter tractability as well as approximation algorithms and we survey several connections between the two areas in terms of both results and approaches. (TCPL 201) |

10:05 - 10:30 | Coffee Break (TCPL Foyer) |

10:30 - 11:00 |
Valia Mitsou: Complexity and Approximability of Parameterized CSP ↓ The complexity of various Constraint Satisfaction Problems (CSP) when parameterized by
structural measures (such as treewidth or clique-width) is a well-investigated area. In this talk, we take
a fresh look at such questions from the point of view of approximation, considering four standard CSP
predicates: AND, OR, PARITY, and MAJORITY. By providing new or tighter hardness results for the
satis ability versions, as well as approximation algorithms for the corresponding maximization problems,
we show that already these basic predicates display a diverse set of behaviors, ranging from being FPT
to optimize exactly for quite general parameters (PARITY), to being W-hard but well-approximable (OR,
MAJORITY) to being W-hard and inapproximable (AND). Our results indicate the interest in posing the
question of approximability during the usual investigation of CSP complexity with regards to the landscape
of structural parameters. This is a joint work with Holger Dell, Eunjung Kim, Michael Lampis, and Tobias Momke. (TCPL 201) |

11:00 - 11:30 |
André Nichterlein: FPT approximation schemes for Shift Bribery ↓ In the Shift Bribery problem, we are given an election (based on preference orders), a preferred
candidate p, and a budget. The goal is to ensure that p wins by shifting p higher in some voters' preference
orders. However, each such shift request comes at a price (depending on the voter and on the extent of the
shift) and we have to minimize the overall costs. In this talk, we show FPT approximation schemes for
the Copeland voting rule (the winner is the candidate winning the most head-to-head competitions) with
respect to each of the parameters number of voters and number of candidates.This is joint work with Robert Bredereck, Jiehua Chen, Piotr Faliszewski, and Rolf Niedermeier. (TCPL 201) |

11:30 - 12:00 |
Frits Spieksma: Balanced Optimization with vector costs ↓ We consider so-called balanced optimization problems with vector costs. We pro- pose a framework
containing such problems; this framework allows us to investigate the complexity and approximability
of these problems in a general setting. More concrete, each problem in the framework admits a
2-approximation, and for many problems within the framework this result is best-possible, in the sense
that having a polynomial-time algorithm with a performance ratio better than 2 would imply P=NP. Special
attention is paid to the balanced assignment problem with vector costs: we show that the problem
remains NP-hard even in case of sum costs. This is joint work with Annette Ficker and Gerhard Woeginger (TCPL 201) |

12:00 - 13:30 | Lunch (Vistas Dining Room) |

15:00 - 15:30 | Coffee Break (TCPL Foyer) |

15:30 - 17:30 | Discussions/Research in groups (TCPL 201) |

17:30 - 19:30 |
Dinner ↓ A buffet dinner is served daily between 5:30pm and 7:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building. (Vistas Dining Room) |

Tuesday, December 1 | |
---|---|

07:00 - 09:00 | Breakfast (Vistas Dining Room) |

09:10 - 10:00 |
Stefan Kratsch: A brief introduction to kernelization ↓ Kernelization is a notion from parameterized complexity that captures the concept of ecient
preprocessing for NP-hard problems. A kernelization is a polynomial-time algorithm that given an instance
(x; k) with parameter k will return an equivalent instance of size bounded only in terms of k. In particular,
we are interested in polynomial kernels where the bound depends polynomially on k.
The talk will give an introduction to core concepts from kernelization. Where appropriate, relations to
approximability of the considered problems will be discussed (TCPL 201) |

10:00 - 10:25 | Coffee Break (TCPL 201) |

10:25 - 10:30 | Group photo (TCPL 201) |

10:30 - 11:00 |
Michael Fellows: Using Parameterization to Move Approximation into Problem Legislation ↓ The talk will give a few examples of moving approximation concerns into the de nition of
parameterized problems | into the modeling of the problem! which is where, considering the nature of
worst-case asymptotic complexity analysis, approximation often realistically belongs. The talk will point
to some large horizons for this approach. (TCPL 201) |

11:00 - 11:30 |
Kati Land: Estimating The Makespan of The Two-Valued Restricted Assignment Problem ↓ We consider a special case of the scheduling problem on unrelated machines, namely the Restricted
Assignment Problem with two dierent processing times. We show that the con guration LP
has an integrality gap of at most 5=3 1:667 for this problem. This allows us to estimate the optimal
makespan within a factor of 5/3 , improving upon the previously best known estimation algorithm with
ratio 11=6 1:833 due to Chakrabarty, Khanna, and Li.
This is joint work with Klaus Jansen and Marten Maack. (TCPL 201) |

11:30 - 12:00 |
Palmo Monaldo Mastrolilli: A Lasserre Lower Bound for the Min-Sum Single Machine Scheduling Problem ↓ The Min-sum single machine scheduling problem (denoted 1jjPfj) generalizes a large number of sequencing problems. The rst constant approximation guarantees have been obtained only recently and are based on natural time-indexed LP relaxations strengthened with the so called Knapsack-Cover inequalities (see Bansal and Pruhs, Cheung and Shmoys and the recent (4 + )-approximation by Mestre and Verschae). These relaxations have an integrality gap of 2, since the Min-knapsack problem is a special case. No APX-hardness result is known and it is still conceivable that there exists a PTAS. Interestingly, the Lasserre hierarchy relaxation, when the objective function is incorporated as a constraint, reduces the
integrality gap for the Min-knapsack problem to 1 + .In this paper we study the complexity of the Min-sum single machine scheduling problem under algorithms from the Lasserre hierarchy. We prove the rst lower bound for this model by showing that the integrality gap is unbounded at level (pn) even for a variant of the problem that is solvable in O(n log n)
time by the Moore-Hodgson algorithm, namely Min-number of tardy jobs. We consider a natural formulation
that incorporates the objective function as a constraint and prove the result by partially diagonalizing
the matrix associated with the relaxation and exploiting this characterization.
Joint work with Adam Kurpisz and Samuli Leppanen. (TCPL 201) |

12:00 - 12:45 | Guided Tour of The Banff Centre (TCPL Foyer) |

12:45 - 13:30 | Lunch (Vistas Dining Room) |

13:30 - 15:00 | Free Time (Banff National Park) |

15:00 - 15:30 | Coffee Break (TCPL Foyer) |

15:30 - 17:30 | Discussions/Reserch in groups (TCPL 201) |

17:30 - 19:30 | Dinner (Vistas Dining Room) |

Wednesday, December 2 | |
---|---|

07:00 - 09:00 | Breakfast (Vistas Dining Room) |

09:30 - 10:00 |
Klaus Jansen: Lower bounds on the running time for packing and scheduling problems ↓ We will present lower bounds on the running time for both exact and approximation algorithms
based on the exponential time hypothesis (ETH). First, we will discuss lower and upper bounds on the
running time for exact algorithms for subset sum, partition, knapsack, bin packing, and scheduling on
identical machines. Next we give lower bounds on the running time of approximation schemes for the multiple
knapsack, multi-dimensional knapsack and scheduling problem on identical, uniform, and unrelated
machines.
This is joint work with Lin Chen, Felix Land, Kati Land, and Guochuan Zhang. (TCPL 201) |

10:00 - 10:30 | Coffee Break (TCPL Foyer) |

10:30 - 11:00 |
Felix Land: A Fully Polynomial (3/2 + ∈)-Approximation for Scheduling Monotone Moldable Jobs ↓ A moldable job is a job that can be executed on an arbitrary number of processors, and whose processing time depends on the number of processors allotted to it. We consider the problem of scheduling
monotone moldable jobs to minimize the makespan. Most existing approximation algorithms have running
time polynomial in the number n of jobs and the number m of processors. We argue that for compact
input encodings, such running times are actually exponential in the input size, and that a fully polynomial
algorithm has a running time polynomial in n and logm. The best known approximation algorithm with
such a running time is due to Mounie, Rapine, and Trystram and achieves approximation ratio
p3 + 1:73. Another algorithm, also due to Mounie, Rapine, and Trystram, has approximation ratio (3/2 + ∈), but
has running time O(nm). We describe dierent techniques to improve the running time of the latter to
polynomial in n and logm. In particular, we show how to solve a knapsack problem with n items and
capacity m in time O(n2log m) when items larger than b = (1) can be compressed by a factor 1().
For our scheduling problem, the compression increases the makespan by a factor of 1+, and we expect a
wide applicability of our techniques.
Furthermore, we prove that scheduling monotone moldable jobs to minimize the makespan in strongly
NP-hard, which was previously known only for the variant without monotony. (TCPL 201) |

11:00 - 11:30 |
Andreas Wiese: Better approximation guarantees for geometric packing problems ↓ A common setting in geometric packing problems is that we are given a set of two-dimensional
items, e.g., rectangles, and a rectangular container and our goal is to pack these items or a subset of them
items into the container to optimize objective functions like the total pro t of the packed items or the
necessary height of the container. A typical obstacle in these problem settings is that in the input there
are dierent types of items, i.e., items that are wide and thin, that are high and narrow, or items that
are large in both dimensions. In this talk, I will present a method to handle this obstacle. In a nutshell,
the key is to prove that there are near-optimal solutions in which the given container can be partitioned
into few rectangular boxes such that in each box there are only items of one of the mentioned types. This
leads to better approximation guarantees for two speci c problems: a (1 + )-approximation algorithm in
quasi-polynomial time for the two-dimensional knapsack problem and a (1:4+)-approximation algorithm
in pseudo-polynomial time for the strip-packing problem. Note that the latter bound is strictly smaller
than the lower bound of 3/2 that holds for (non-pseudo-)polynomial time algorithms for the problem.
Joint work with Anna Adamaszek and Giorgi Nadiradze (TCPL 201) |

11:30 - 12:00 |
Nicole Megow: An O(log m)-Competitive Algorithm for Online Machine Minimization ↓ We consider the online machine minimization problem in which jobs with hard deadlines arrive
online over time at their release dates. The task is to determine a feasible preemptive schedule on a
minimum number of machines. Our main result is an O(logm)-competitive algorithm, with m being
the optimal number of machines used in an optimal oine solution. This is the rst improvement on an
intriguing problem in nearly two decades. To date, the best known result is a O(log pmin=pmax)-competitive
algorithm by Phillips et al. (STOC 1997) that depends on the ratio of maximum and minimum job sizes,pmax and pmin. Even for m = 2 no better algorithm was known. Our algorithm is in this case constantcompetitive.
When applied to laminar or agreeable instances, our algorithm achieves a competitive ratio of
O(1) even independently of m. The following two key components lead to our new result. Firstly, we derive
a new lower bound on the optimum value that relates the laxity and the number of jobs with intersecting
time windows. Then, we design a new algorithm that is tailored to this lower bound and balances the
delay of jobs by taking the number of currently running jobs into account.
Joint work with Lin Chen and Kevin Schewior. (TCPL 201) |

12:00 - 13:30 | Lunch (Vistas Dining Room) |

13:30 - 17:30 | Free Afternoon (Banff National Park) |

17:30 - 19:30 | Dinner (Vistas Dining Room) |

Thursday, December 3 | |
---|---|

07:00 - 09:00 | Breakfast (Vistas Dining Room) |

09:30 - 10:00 |
Guochuan Zhang: Packing group items ↓ We consider a natural generalization of the classical multiple knapsack problem where instead
of packing single items we are packing groups of items. In this setting, we have multiple knapsacks of unit
capacity, and a set of items, each of a size within (0,1]. These items appear in groups, where each group is
associated with a pro t. The pro t can be attained if and only if every item of this group is packed into the
knapsacks. Such a general model nds applications in delivering bundles of goods. Apart from that, the
theoretical issue is of particular interests. It is obvious that no nite bounds are possible, unless P=NP, if
a group size (the total size of items in the group) can be arbitrarily large. We thus pay attention to the
parameterized version while every group size is bounded by a factor of the total capacity of knapsacks.
Along this line, we provide deep insights into the approximability with respect to the factor and derive,
respectively, approximation algorithms and inapproximability results.
Joint work with Lin Chen. (TCPL 201) |

10:00 - 10:30 | Coffee Break (TCPL Foyer) |

10:30 - 11:00 |
Matthias Mnich: Improved Approximation Algorithm for Minimum Feedback Vertex Sets in Tournaments ↓ We consider the minimum feedback vertex set problem in tournaments, which nds applications
in ranking scenarios. This problem is NP-hard to solve exactly, and Unique Games-hard to approximate
by a factor better than two. We present an approximation algorithm for this problem that improves on
the previously best known ratio 5/2, given by Cai et al. in FOCS 1998 / SICOMP 2001.
Joint work with Laszlo A. Vegh (London School of Economics and Political Science). (TCPL 201) |

11:00 - 11:30 |
Sebastian Berndt: Fully Dynamic Bin Packing Revisited ↓ We consider the fully dynamic bin packing problem, where items arrive and depart in an online
fashion and repacking of previously packed items is allowed. The goal is to minimize both the number of
bins used as well as the amount of repacking. We measure the repacking by the migration factor, de ned
as the total size of repacked items divided by the size of an arriving or departing item. If one wishes to
achieve an asymptotic competitive ration of 1 + for the number of bins, a relatively simple argument
proves a lower bound of
(1=) for the migration factor. We establish a nearly matching upper bound
of O((1=)4 log(1=)) using a new dynamic rounding technique and new ideas to handle small items in a
dynamic setting such that no amortization is needed. The running time of our algorithm is polynomial in
the number of items n and in 1=. The previous best trade-o was for an asymptotic competitive ratio of
5=4 for the bins (rather than 1 + ) and needed an amortized number of O(log n) repackings (while in our
scheme the number of repackings is independent of n and non-amortized).
Joint work with Klaus Jansen and Kim-Manuel Klein (TCPL 201) |

11:30 - 12:00 |
Liming Cai: Maximum Spanning k-Tree: A Case Study ↓ The Maximum Spanning Backbone k-Tree (BkT) problem, for k 2, is to nd a maximum
weight spanning k-tree from the input edge-weighted graph with a designated Hamiltonian path to be
desired in the output spanning graph. Originally motivated by research in bio-molecular 3D structure
prediction, BkT turns out a typical problem in a new class of languages de nable beyond Monadic Second
Order logic. We show that, unlike the Maximum Spanning k-Tree problem that is NP-hard for even k = 2,
the BkT problem is solvable in time O(nk+1), for every xed k 2. While there is evidence of diculty to
improve the polynomial degree k + 1 to any number lower, we show that there are O(n3)-time algorithms
to approximate the BkT problem to the ratio k(k 1), for every xed k 3. The tractability results
also hold with the constraint of a designated spanning tree instead of a designated Hamiltonian path, a
scenario that often arises in learning of Markov networks of bounded tree width.
This presentation includes some joint works with L. Ding, X. Huang, G. Li, R. Malmberg, B. Robinson,
A. Samad, and X. Xue. (TCPL 201) |

12:00 - 13:30 | Lunch (Vistas Dining Room) |

13:30 - 15:00 | Free Time (Banff National Park) |

14:02 - 14:04 | Frances Rosamond: The FPT wiki (TCPL 201) |

15:00 - 15:30 | Coffee Break (TCPL Foyer) |

15:30 - 17:30 | Discussions/Research in groups (TCPL 201) |

17:30 - 19:30 | Dinner (Vistas Dining Room) |

Friday, December 4 | |
---|---|

07:00 - 09:00 | Breakfast (Vistas Dining Room) |

09:30 - 10:00 |
Martin Fürer: Multi-Clique-Width, a Powerful New Width Parameter ↓ Multi-clique-width is obtained by a simple modi cation in the de nition of clique-width. It has
the advantage of providing a natural extension of tree-width. Unlike clique-width, it does not explode
exponentially compared to tree-width. Ecient algorithms based on multi-clique-width are still possible
for interesting tasks like computing the independent set polynomial or testing c-colorability. In particular,
c-colorability can be tested in time linear in n and singly exponential in c and the width k of a given
multi-k-expression. For these tasks, the running time as a function of the multi-clique-width is the same
as the running time of the fastest known algorithm as a function of the clique-width. This results in an
exponential speed-up for some graphs, if the corresponding graph generating expressions are given. The
reason is that the multi-clique-width is never bigger, but is exponentially smaller than the clique-width for
many graphs. (TCPL 201) |

10:00 - 10:30 | Coffee Break (TCPL Foyer) |

10:30 - 11:00 |
Thomas Erlebach: On Temporal Graph Exploration ↓ A temporal graph is a graph in which the edge set can change from step to step. The temporal
graph exploration problem TEMPEX is the problem of computing a foremost exploration schedule for a
temporal graph, i.e., a temporal walk that starts at a given start node, visits all nodes of the graph, and
has the smallest arrival time. We consider only temporal graphs that are connected at each step. For such
temporal graphs with n nodes, we show that it is NP-hard to approximate TEMPEX with ratio O(n1)
for any > 0. We also provide an explicit construction of temporal graphs that require (n2) steps to
be explored. We then consider TEMPEX under the assumption that the underlying graph (i.e. the graph
that contains all edges that are present in the temporal graph in at least one step) belongs to a speci c
class of graphs. Among other results, we show that temporal graphs can be explored in O(n1:5k2 log n)
steps if the underlying graph has treewidth k and in O(n log3 n) steps if the underlying graph is a 2 grid. We also show that sparse temporal graphs with regularly present edges can always be explored in
O(n) steps.
Joint work with Michael Homann and Frank Kammer. (TCPL 201) |

11:00 - 11:30 | Discussion/Research in groups (TCPL 201) |

11:30 - 12:00 |
Checkout by Noon ↓ 5-day workshop participants are welcome to use BIRS facilities (BIRS Coffee Lounge, TCPL and Reading Room) until 3 pm on Friday, although participants are still required to checkout of the guest rooms by 12 noon. (Front Desk - Professional Development Centre) |

12:00 - 13:30 | Lunch from 11:30 to 13:30 (Vistas Dining Room) |