Schedule for: 15w5118 - Approximation Algorithms and Parameterized Complexity

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.

Breakfast is served daily between 7 and 9am in the Vistas Dining Room, the top floor of the Sally Borden Building.

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.

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.

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.

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

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.

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

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.

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.

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.

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.

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.

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

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.

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.

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

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

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.

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.

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.

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.