Monday, November 13 |
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:00 - 10:00 |
Rico Zenklusen: Bimodular Integer Linear Programming and Beyond ↓ In this talk, I will show how any integer linear program (ILP) defined by a constraint matrix whose subdeterminants are all within {-2,-1,0,1,2} can be solved efficiently; even in strongly polynomial time. This is a natural extension of the well-known fact that ILPs with totally unimodular (TU) constraint matrices are polynomial-time solvable, which readily follows by the natural integrality of polytopes defined by a TU constraint matrix and integral right-hand sides.
To derive this result we combine several techniques. In particular, the problem is first reduced to a particular parity-constrained ILP over a TU constraint matrix. We then leverage Seymour's decomposition of TU matrices to break this parity-constrained ILP into simpler base problems. Finally, we show how these base problems can be solved efficiently by combinatorial optimization techniques, including parity-constrained submodular minimization, and how to derive an optimal solution to the initial ILP from optimal solutions to base problems. Moreover, I will highlight some of the many open problems in this field and discuss recent results related to possible extensions to larger subdeterminants. (TCPL 201) |
10:00 - 10:30 |
Coffee Break (TCPL Foyer) |
10:30 - 11:00 |
Chaitanya Swamy: Improved Algorithms for MST and Metric-TSP Interdiction ↓ Interdiction problems investigate the sensitivity of an underlying optimization problem with respect to removal of a limited set of underlying elements in order to identify vulnerable spots for possible reinforcement or disruption. We consider the MST-interdiction problem: given a multigraph G with weights and interdiction costs on the edges, and an interdiction budget B, find a set R of edges of total interdiction cost at most B so as to maximize the weight of an MST of G-R.
Our main result is a 4-approximation algorithm for this problem. This improves upon the previous-best 14-approximation due to Zenklusen, and notably, our analysis is also significantly simpler and cleaner. Whereas Zenklusen uses a greedy algorithm with an involved analysis to extract a good interdiction set from an over-budget set, we utilize a generalization of knapsack called the tree knapsack problem that nicely captures the key combinatorial aspects of this "extraction problem." We prove a simple, yet strong, LP-relative approximation bound for tree knapsack, which leads to our improved guarantees for MST interdiction. Our algorithm and analysis are nearly tight, as we show that one cannot achieve an approximation ratio better than 3 relative to the upper bound used in our (and the prior) analysis. Our guarantee for MST-interdiction yields an 8-approximation for metric-TSP interdiction. We also show that the maximum-spanning-tree interdiction problem is at least as hard to approximate as the minimization version of densest-k-subgraph.
This is joint work with Andre Linhares. (TCPL 201) |
11:00 - 11:30 |
Cedric Koh: Stabilizing Weighted Graphs ↓ An edge-weighted graph G is called stable if the value of a maximum-weight matching equals the value of a maximum-weight fractional matching. Stable graphs play an important role in some interesting game theory problems, such as network bargaining games and cooperative matching games, because they characterize instances which admit stable outcomes. Motivated by this, in the last few years many researchers have investigated the algorithmic problem of turning a given graph into a stable one, via edge- and vertex-removal operations. However, all the algorithmic results developed in the literature so far only hold for unweighted instances, i.e., assuming unit weights on the edges of G.
We give the first polynomial-time algorithm to find a minimum cardinality subset of vertices whose removal from G
yields a stable graph, for any weighted graph G.
The algorithm is combinatorial and exploits new structural properties of basic fractional matchings, which may be of independent interest.
In contrast, we show that the problem of finding a minimum cardinality subset of edges whose removal from a weighted graph G
yields a stable graph, does not admit any constant-factor approximation algorithm, unless P=NP.
In this setting, we develop an O(Delta)-approximation algorithm for the problem, where Delta is the maximum degree of a node in G. (TCPL 201) |
11:30 - 13:00 |
Lunch ↓ Lunch is served daily between 11:30am and 1:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building. (Vistas Dining Room) |
14:00 - 14:20 |
Group Photo ↓ Meet in foyer of TCPL to participate in the BIRS group photo. The photograph will be taken outdoors, so dress appropriately for the weather. Please don't be late, or you might not be in the official group photo! (TCPL Foyer) |
15:00 - 15:30 |
Coffee Break (TCPL Foyer) |
15:30 - 16:00 |
Yury Makarychev: Algorithms for Stable and Perturbation-Resilient Problems ↓ We study the notion of stability and perturbation resilience introduced by Bilu and Linial (2010) and Awasthi, Blum, and Sheffet (2012). A combinatorial optimization problem is α-stable or α-perturbation-resilient if the optimal solution does not change when we perturb all parameters of the problem by a factor of at most α. We present improved algorithms for stable instances of various clustering and optimization problems, including k-means, k-median, Max Cut, and Minimum Multiway Cut. We also show several hardness results.
The talk is based on joint papers with Haris Angelidakis, Konstantin Makarychev, and Aravindan Vijayaraghavan. (TCPL 201) |
16:00 - 16:30 |
Parinya Chalermsook: From Gap-ETH to FPT Inapproximability: Clique, Dominating Set, and More ↓ Finding k-clique in a graph can trivially be done in time n^{O(k)}, and this is more or less tight if one assumes the Exponential Time Hypothesis (ETH). Now, given the existence of a clique of much larger size, e.g. exp(exp(exp(k))), can we find a k-clique much faster?
Similar questions can be asked for maximum dominating set, maximum induced planar subgraph, and many other problems of this nature. In this work, we show that the answers for these questions are likely to be negative: An n^{o(k)} time algorithm for many of these problems will break the Gap-ETH assumption [Dinur'16, Manurangsi-Raghavendra'16], i.e., it will imply 0.99 approximation for 3SAT that runs in sub-exponential time. Breaking Gap-ETH seems beyond the reach of current algorithmic techniques.
[joint work with M. Cygan, G. Kortsarz, B. Laekhanukit, P. Manurangsi, D. Nanongkai, L. Trevisan, to appear in FOCS 2017] (TCPL 201) |
16:30 - 17:00 |
Bundit Laekhanukit: (Almost) Settling the Complexity of Approximating Parameterized Dominating Set. ↓ In this talk, we discuss the parameterized complexity of approximating the k-Dominating Set problem, where we are asked to decide whether an input graph G on n vertices has a dominating set of size F(k) * k in time T(k) * poly(n). In particular, we consider the question of whether there is an FPT-approximation algorithm for the k-Dominating Set problem. We show that, unless FPT=W[1], the k-Dominating Set problem admits no such FPT-approximation algorithm, for any non-decreasing functions F and T depending only on k (which can be tower functions). Furthermore, we show that, assuming ETH, the k-Dominating Set problem admits no (log n)^{1/k} approximation algorithm that runs in time n^{o(k)}.
Our results are obtained from parameterized PCPs for k-Clique constructed by a simple coding technique.
This is a joint work with Pasin Manurangsi (UC Berkeley) and Karthik CS (Weizmann Institute of Science), and it is a continuation of a talk from Parinya, which shows the same result under Gap-ETH. (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) |