Schedule for: 23w5140 - Approximation Algorithms and the Hardness of Approximation

A buffet dinner is served daily between 5:30pm and 7:30pm in Vistas Dining Room, top floor of the Sally Borden Building.

BIRS Lounge on the 2nd floor of PDC.

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

A brief introduction to BIRS with important logistical information, technology instruction, and opportunity for participants to ask questions.

The Weighted Connectivity Augmentation Problem (WCAP) asks to increase the edge-connectivity of a graph in the cheapest possible way by adding edges from a given set. It is one of the most elementary network design problems for which no better-than-2 approximation algorithm has been known, whereas 2-approximations can be easily obtained through a variety of well-known techniques. In this talk, I will discuss an approach showing that approximation factors below 2 are achievable for WCAP, ultimately leading to a (1.5 + ε)-approximation algorithm. Our approach is based on a highly structured directed simplification of WCAP with planar optimal solutions. We show how one can successively improve solutions of this directed simplification by moving to mixed-solutions, consisting of both directed and undirected edges. These insights can be leveraged in local search and relative greedy strategies, inspired by recent advances on the Weighted Tree Augmentation Problem, to obtain a (1.5 + ε)-approximation algorithm for WCAP.

In the strong form of the thin tree conjecture, formulated by Goddyn in 2004, we are given a k-edge-connected graph and wish to find a tree containing at most an O(1/k) fraction of the edges across every cut. This conjecture, if true, has a variety of implications in a number of areas such as graph theory and approximation algorithms. A natural relaxation of this problem is to find a tree with at most O(1/k) edges across a fixed collection of cuts, instead of all cuts. Using iterative relaxation, combined with a simple reduction technique, we show that the thin tree conjecture is true whenever the specified cuts form a laminar family.

The Survivable Network Design problem (SNDP) is a well-studied network design problem generalizing many classical problems, including Steiner Tree and kECSS. This model is motivated in part by robustness to faults under the assumption that any subset of edges upto a specific number can fail. This talk considers non-uniform models, where the subset of edges that fail can be specified in different ways. Our primary interests are the flexible graph connectivity model and the bulk-robust network design model. While SNDP admits a 2-approximation, the approximability of problems in these more complex models is much less understood even in special cases. In the flexible graph connectivity model, the edge set is partitioned into safe and unsafe edges. Given parameters p and q, the goal is to find a cheap subgraph that remains p-connected even after the failure of q unsafe edges. Motivated by a conjecture that a constant factor approximation is feasible when p and q are fixed, we consider two special cases: single pair and global. In both cases, we obtain approximation ratios that depend only on p and q for small values of p,q. These are based on an augmentation framework and decomposing the families of cuts that need to be covered into a small number of uncrossable families. In the bulk-robust model, we are given "scenarios" of subsets of edges that could fail, and the goal is to find a cheap subgraph that remains connected even after the failure of any scenario. We give the first poly-logarithmic approximation for this problem when the maximum number of edges in any scenario is fixed. We utilize a recent framework designed for group connectivity using congestion-based tree embeddings.

Lunch is served daily between 11:30am and 1:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building.

Meet at Vistas for a guided tour of The Banff Centre campus.

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!

We address long-standing open questions raised by Williamson, Goemans, Vazirani and Mihail pertaining to the design of approximation algorithms for problems in network design via the primal-dual method (Combinatorica 15(3):435-454, 1995). Williamson et al. prove an approximation guarantee of two for connectivity augmentation problems where the connectivity requirements can be specified by so-called uncrossable functions. They state: “Extending our algorithm to handle non-uncrossable functions remains a challenging open problem. The key feature of uncrossable functions is that there exists an optimal dual solution which is laminar. This property characterizes uncrossable functions... A larger open issue is to explore further the power of the primal-dual approach for obtaining approximation algorithms for other combinatorial optimization problems.” Our main result proves an O(1)-approximation guarantee via the primal-dual method for a class of functions that generalizes the notion of an uncrossable function. We mention that the support of every optimal dual solution could be non-laminar for instances that can be handled by our methods. We present two applications of our main result: 1. An O(1)-approximation algorithm for augmenting the family of near-minimum cuts of a graph. 2. An O(1)-approximation algorithm for the model of (p, 2)-Flexible Graph Connectivity. This is joint work with Joseph Cheriyan, Logan Grout and Sharat Ibrahimpur and has appeared at ICALP'23.

A spanning tree $T$ of graph $G$ is a $\rho$-approximate \emph{universal Steiner tree} (UST) for root vertex $r$ if, for any subset of vertices $S$ containing $r$, the cost of the minimal subgraph of $T$ connecting $S$ is within a $\rho$ factor of the minimum cost tree connecting $S$ in $G$. Busch et al.\ showed that USTs are equivalent to strong sparse partition hierarchies (up to poly-logarithmic factors). Further, they posed poly-logarithmic USTs and strong sparse partition hierarchies as open questions. In this talk, I will discuss a polynomial-time algorithm to compute $O(\log^7 n)$-approximate USTs via poly-logarithmic strong sparse partition hierarchies. We reduce the existence of these objects to the previously studied cluster aggregation problem and what we call dangling nets. This talk is based on the paper by the same name (FOCS'23); joint work with Costas Busch, Da Qi Chen, Arnold Filtser, D. Ellis Hershkowitz, and Rajmohan Rajaraman.

In the Directed Steiner Tree (DST) problem, we are given a directed graph with edge costs, a set of terminal nodes, and a root node r. The goal is to find a minimum-cost branching rooted at r in which every terminal is reachable from the root. DST is a common generalization of many important problems in combinatorial optimization including Set Cover and Group Steiner Tree. However, this generalization comes at a cost; optimal DST solutions are notoriously hard to even approximate, i.e., the known gap between the algorithmic result and the hardness result is exponential. In this talk, I will discuss a simple combinatorial O(log k)-approximation for DST when the input graph is planar. If time permits, I also present a primal-dual based constant factor approximation for the quasi-bipartite DST on minor-free graphs, where in quasi-bipartite DST instances there are no edges between two non-terminal nodes. This is joint work with Zachary Friggstad.

A buffet dinner is served daily between 5:30pm and 7:30pm in Vistas Dining Room, 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.

Constraint Satisfaction Problems (CSPs) are among the most well-studied problems in Computer Science. The satisfiability problem for CSP asks whether an instance of CSP has a fully satisfying assignment, i.e. an assignment that satisfies all constraints. This problem is known to be in class P or is NP-complete by the recently proved Dichotomy Theorem of Bulatov and Zhuk. For a given k-ary predicate $P: [q]^k -> \{0,1\}$, where $P^{-1}(1)$ denotes the set of satisfying assignments, the problem CSP(P) has every local constraints of the form the predicate P applied to the ordered set of k variables (or literals). A most natural question is to ask for the precise threshold $\alpha(P)$ less than 1 for every NP-complete CSP(P) such that (i) there is a polynomial-time algorithm that finds an assignment satisfying $\alpha(P)$ fraction of the constraints on a satisfiable instance and (ii) for every \epsilon greater than 0, finding an $(\alpha(P)+\epsilon)$ satisfying assignment is NP-hard. It is reasonable to hypothesize that such a threshold exists for every NP-complete CSP(P). This natural question is wide open, though such thresholds are known for some specific predicates (e.g., 7/8 for 3SAT by Hastad). The talk will present recent work initiating a systematic study of this question, a relevant analytic hypothesis and some progress on it, and a work of Raghavendra that answers the question on almost-satisfiable instances. The talk will be based on a series of joint works with Subhash Khot and Dor Minzer.

Does a random walk on an expander mix when the randomness comes from a weak randomness source? It was folklore that the answer was “NO”, since an adversary who only controls every other step can keep the walk around its starting point. In this paper we show that if there’s a little bit of fresh randomness in each step the walk does mix. This is so, even though such a walk is no longer Markovian and standard spectral techniques fail to analyze it. Our analysis is based on the l1+e-norm and could be of independent interest. Randomness sources where each step contains a little fresh entropy (known as Santha-Vazirani/Chor-Goldreich sources) were the first sources considered in the extractor community back in the 1980’s. It was known that one cannot extract nearly uniform bits from them deterministically. Yet we show that one can extract from them bits with nearly full entropy deterministically! The proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC23)

A $\mu$-biased Max-CSP instance with predicate $\psi:\{0,1\}^r \to \{0,1\}$ is an instance of Constraint Satisfaction Problem (CSP) where the objective is to find a labeling of relative weight at most $\mu$ which satisfy the maximum fraction of constraints. Biased CSPs are versatile and express several well-studied problems such as Densest-$k$-Sub(Hyper)graph and SmallSetExpansion. In this work, we explore the role played by the bias parameter $\mu$ in the approximability of biased CSPs. We show that the approximability of such CSPs can be characterized (up to loss of factors in arity $r$) using the bias-approximation curve of Densest-$k$-SubHypergraph (DkSH) problems. In particular, this gives a tight characterization of predicates that admit approximation guarantees that are independent of the bias parameter $\mu$. Motivated by the above, we give new approximation and hardness results for DkSH -- our upper and lower bounds are tight up to constant factors, when the arity $r$ is a constant, and in particular, imply the first tight approximation bounds for the Densest-$k$-Subgraph problem in the constant bias regime. Furthermore, using the above characterization, our results also imply matching algorithms and hardness for every biased CSP of constant arity. This is joint work with Euiwoong Lee.

In a breakthrough result, Raghavendra showed assuming UGC that semidefinite programming obtains an optimal polynomial-time approximation ratio for every MAX CSP. However, for many natural MAX CSPs (such as MAX SAT), we still do not know how to practically compute the optimal approximation ratio. In this talk, I will discuss some of these open questions about MAX CSPs as well as present the following results (assuming UGC): (1) The approximation constant for MAX NAE-SAT is at most 0.8739 < 7/8. (2) The approximation constant for MAX DI-CUT is strictly between the approximation constants for MAX 2-AND and MAX CUT, answering questions of Austrin and Feige-Goemans. These results are obtain via a combination of theoretical and computational methods. Based on joint works with Neng Huang, Aaron Potechin, and Uri Zwick

Lunch is served daily between 11:30am and 1:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building.

The joint replenishment problem is a classical inventory management problem, where we seek to balance the cost incurred by a fixed ordering overhead with the cost of maintaining on-hand inventory: we have a set of item types, for which there is specified demand over a finite, discrete-time horizon; placing any order at a given time incurs a general ordering cost and item-specific ordering costs (independent of the total demand serviced); in addition, there is a corresponding item-specific holding cost incurred that is a function of the length of time held; the aim is to minimize the total cost. In practice, not all demand can be met, and some orders are rejected. Our motivation is to study algorithms where these rejections are handled fairly. We consider a setting in which there are C colors (corresponding to markets) and we constrain the solutions to a given total rejection bound for each color class. We give the first constant approximation algorithms for this class of problems (and even a generalization in which there a notion of a C-dimensional feature vector associated with each demand point). As a by-product, we also improve upon known constants achievable for the case with C=1, when we simply bound the number of rejections allowed. This is joint work with Varun Suriyanarayana, Varun Sivashankar, and Siddharth Gollapudi.

In a seminal paper, Kannan and Lov\'asz (1988) considered a quantity $\mu_{KL}(\Lambda,K)$ which denotes the best volume-based lower bound on the \emph{covering radius} $\mu(\Lambda,K)$ of a convex body $K$ with respect to a lattice $\Lambda$. Kannan and Lov\'asz proved that $\mu(\Lambda,K) \leq n \cdot \mu_{KL}(\Lambda,K)$ and the Subspace Flatness Conjecture by Dadush (2012) claims a $O(\log n)$ factor suffices, which would match the lower bound from the work of Kannan and Lov\'asz. We settle this conjecture up to a constant in the exponent by proving that $\mu(\Lambda,K) \leq O(\log^{3}(n)) \cdot \mu_{KL} (\Lambda,K)$. Our proof is based on the Reverse Minkowski Theorem due to Regev and Stephens-Davidowitz (2017). Following the work of Dadush (2012, 2019), we obtain a $(\log n)^{O(n)}$-time randomized algorithm to solve integer programs in $n$ variables. Another implication of our main result is a near-optimal \emph{flatness constant} of $O(n \log^{4}(n))$. This is joint work with Victor Reis.

Two complementary facets of the online bipartite matching problem are discussed. (1) For numerous online bipartite matching problems, such as edge-weighted matching and matching under two-sided vertex arrivals, state-of-the-art fractional algorithms outperform their randomized integral counterparts. Thus, a natural question is whether we can achieve lossless online rounding of fractional solutions in this setting. Even though lossless online rounding is impossible in general, randomized algorithms do induce fractional algorithms of the same competitive ratio, which by definition are losslessly roundable online. This motivates the addition of constraints that decrease the ``online integrality gap'', thus allowing for lossless online rounding. We characterize a set of non-convex constraints which allow for such lossless online rounding and allow for better competitive ratios than yielded by deterministic algorithms. (2) In a different vein, we study the problem of rounding fractional bipartite matchings in online settings. We assume that a fractional solution is already generated for us online by a black box (via a fractional algorithm, or some machine-learned advice) and provided as part of the input, which we then wish to round. We provide improved bounds on the rounding ratio and discuss several applications. Based on joint papers with Niv Buchbinder, Aravind Srinivasan, and David Wajc.

The GHZ game, also known as the “quantum telepathy game”, is an example of a 3-player game in which classical strategies have winning chances of at most 3/4, whereas there are available quantum strategies that succeed with probability 1. In this talk, we will discuss the “parallel repetition” of the GHZ game, in which the players play several copies of the game in parallel. We will describe the analysis of parallel repetition of the GHZ game and discuss somewhat a surprising connection to groups, additive combinatorics and analysis.

A buffet dinner is served daily between 5:30pm and 7:30pm in Vistas Dining Room, 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.

Given subsets of uncertain values, we study the problem of identifying the subset of minimum total value by querying as few values as possible. This set selection problem falls into the field of explorable uncertainty and is of intrinsic importance therein as it implies strong adversarial lower bounds for a wide range of classical problems such as knapsack and matchings. We consider a stochastic problem variant and give algorithms that, in expectation, improve upon these adversarial lower bounds. The key to our results is to prove a strong structural connection to a seemingly unrelated covering problem with uncertainty in the constraints via a linear programming formulation. We exploit this connection to derive an algorithmic framework that can be used to solve both problems under uncertainty, obtaining nearly tight bounds on the competitive ratio. This is the first non-trivial stochastic result concerning the sum of unknown values without further structure known for the set and it may by useful for solving more general problems in the area of explorable uncertainty. Joint work with Jens Schlöter, IPCO 2023

We revisit the \textsc{a priori TSP} (with independent activation) and prove stronger approximation guarantees than were previously known. In the \textsc{a priori TSP}, we are given a metric space $(V,c)$ and an activation probability $p(v)$ for each customer $v\in V$. We ask for a TSP tour $T$ for $V$ that minimizes the expected length after cutting $T$ short by skipping the inactive customers. All known approximation algorithms select a nonempty subset $S$ of the customers and construct a \emph{master route solution}, consisting of a TSP tour for $S$ and two edges connecting every customer $v\in V\setminus S$ to a nearest customer in $S$. We address the following questions. If we randomly sample the subset $S$, what should be the sampling probabilities? How much worse than the optimum can the best master route solution be? The answers to these questions (we provide almost matching lower and upper bounds) lead to improved approximation guarantees: less than 3.1 with randomized sampling, and less than 5.9 with a deterministic polynomial-time algorithm. This is joint work with Jannis Blauth, Meike Neuwohner, and Luise Puhlmann.

A long-standing conjecture for the traveling salesman problem (TSP) states that the integrality gap of the standard linear programming relaxation of the TSP (sometimes called the Subtour LP or the Held-Karp bound) is at most 4/3 for symmetric instances of the TSP obeying the triangle inequality; that is, the cost of an optimal tour is at most 4/3 times the value of the value of the corresponding linear program. It has long been known that the integrality gap is at most 3/2. Despite significant efforts by the community, the conjecture remains open. In this talk, I consider the half-integral case, in which a feasible solution to the LP has solution values in {0, 1/2, 1}. Such instances have been conjectured to be the most difficult instances for the overall four-thirds conjecture. Karlin, Klein, and Oveis Gharan, in a breakthrough result, were able to show that in the half-integral case, the integrality gap is at most 1.49993; Gupta et al. showed a slight improvement of this result to 1.4983. Additionally, this result led to the first significant progress on the overall conjecture in decades; the same authors showed the integrality gap of the Subtour LP is at most 1.5-epsilon for some epsilon > 10^{-36}. With the improvements on the 3/2 bound remaining very incremental, even in the half-integral case, we turn the question around and look for a large class of half-integral instances for which we can prove that the 4/3 conjecture is correct, preferably one containing the known worst-case instances. In Karlin et al.'s work on the half-integral case, they perform induction on a hierarchy of critical tight sets in the support graph of the LP solution, in which some of the sets correspond to cycle cuts and the others to degree cuts. Here we show that if all the sets in the hierarchy correspond to cycle cuts, then we can find a distribution of tours whose expected cost is at most 4/3 times the value of the half-integral LP solution; sampling from the distribution gives us a randomized 4/3-approximation algorithm. We note that known bad cases for the integrality gap have a gap of 4/3 and have a half-integral LP solution in which all the critical tight sets in the hierarchy are cycle cuts; thus our result is tight. This work is joint with Billy Jin (Cornell) and Nathan Klein (Washington).

The Parameterized Inapproximability Hypothesis (PIH) is the analog of the PCP theorem in the world of parameterized complexity. It asserts that no FPT algorithm can distinguish a satisfiable 2CSP instance from one which is only $(1-\varepsilon)$-satisfiable (where the parameter is the number of variables) for some constant $0<\varepsilon<1$. We consider a minimization version of CSPs (Min-CSP), where one may assign $r$ values to each variable, and the goal is to ensure that every constraint is satisfied by some choice among the $r \times r$ pairs of values assigned to its variables (call such a CSP instance $r$-list-satisfiable). We prove the following strong parameterized inapproximability for Min CSP: For every $r \ge 1$, it is W[1]-hard to tell if a 2CSP instance is satisfiable or is not even $r$-list-satisfiable. We refer to this statement as "Baby PIH", following the recently proved Baby PCP Theorem. Our proof adapts the combinatorial arguments underlying the Baby PCP theorem, overcoming some significant obstacles that arise in the parameterized setting. An extension of our result to an average-version of Baby PIH would prove the inapproximability of parameterized $k$-ExactCover, a notorious open problem.

The k-Steiner-2NCS problem is as follows: Given a constant k, and an undirected connected graph G=(V,E), non-negative edge costs, and a partition (T, V−T) of V into a set of terminals, T, and a set of non-terminals (or, Steiner nodes), where |T|=k, find a minimum-cost two-node connected subgraph that contains the terminals. We present a randomized polynomial-time algorithm for the unweighted problem, and a randomized PTAS for the weighted problem. Our methods build on results by Björklund, Husfeldt, and Taslaman (ACM-SIAM SODA 2012) that give a randomized polynomial-time algorithm for the unweighted k-Steiner-cycle problem; this problem has the same inputs as the unweighted k-Steiner-2NCS problem, and the algorithmic goal is to find a minimum size simple cycle C that contains the terminals. (joint work with Bansal, Grout, Ibrahimpur)

Lunch is served daily between 11:30am and 1:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building.

In the cutwidth problem, aka minimum cut linear arrangement, we are given a graph G and the goal is to order the vertices in a line such that the maximum number of edges crossing any vertex v is minimized. Since the seminal work of Leighton and Rao, the best known LP-based approximation for the problem is $O(log^2 n)$, based on recursively finding balanced separators (this directly improves to $O(\log^{1.5} n)$ if we use ARV to find the separators). In this talk, I will describe a $\log^{1+o(1)} n LP-based approximation for the problem. Based on joint work with Dor Katzelnik and Roy Schwartz.

We consider the classic Correlation Clustering problem: Given a complete graph where edges are labelled either + or -, the goal is to find a partition of the vertices that minimizes the number of the +edges across parts plus the number of the -edges within parts. Recently, Cohen-Addad, Lee and Newman presented a 1.994-approximation algorithm for the problem using the Sherali-Adams hierarchy, hence breaking through the integrality gap of 2 for the classic linear program and improving upon the 2.06-approximation of Chawla, Makarychev, Schramm and Yaroslavtsev. We significantly improve the state-of-the-art by providing a 1.73-approximation for the problem. Our approach introduces a preclustering of Correlation Clustering instances that allows us to essentially ignore the error arising from the correlated rounding used by Cohen-Addad et al. This additional power simplifies the previous algorithm and analysis. More importantly, it enables a new set-based rounding that complements the previous roundings. A combination of these two rounding algorithms yields the improved bound. This is based on joint work with Cohen-Addad, Lee and Newman.

In the Submodular Facility Location problem (SFL) we are given a collection of n clients and m facilities in a metric space. A feasible solution consists of an assignment of each client to some facility. For each client, one has to pay the distance to the associated facility. Furthermore, for each facility f to which we assign the subset of clients Sf, one has to pay the opening cost g(Sf), where g(⋅) is a monotone submodular function with g(∅)=0. SFL is APX-hard since it includes the classical (metric uncapacitated) Facility Location problem (with uniform facility costs) as a special case. Svitkina and Tardos [SODA'06] gave the current-best O(logn) approximation algorithm for SFL. The same authors pose the open problem whether SFL admits a constant approximation and provide such an approximation for a very restricted special case of the problem. We make some progress towards the solution of the above open problem by presenting an O(loglogn) approximation. We also obtain an improved approximation algorithm for the related Universal Stochastic Facility Location problem.

A buffet dinner is served daily between 5:30pm and 7:30pm in Vistas Dining Room, 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.

Many clustering problems are NP-hard and therefore extensive research has gone into designing approximation algorithms for these problems. Indeed, many techniques in approximation algorithms have been honed in the study of many of these fundamental problems. In this talk, I will talk about a technique called the “round-or-cut technique” (also called the “cutting plane technique” in integer programming parlance) which is probably not as well-known as many other techniques in approximation algorithms. In the last five years, however, this technique has led to tractable approximation algorithms for many clustering problems. I would like to present this general technique and illustrate it on (at least?) one such clustering problem.

We develop a framework for designing approximation algorithms for a wide class of (1-stage) stochastic-optimization problems with norm-based objective functions. We introduce the model of stochastic minimum-norm combinatorial optimization, wherein the costs involved are random variables with given distributions, and we are given a monotone, symmetric norm f. Each feasible solution induces a random multidimensional cost vector whose entries are independent random variables, and the goal is to find a solution that minimizes the expected f-norm of the induced cost vector. This is a very rich class of objectives, containing all l_p norms, as also Top-l norms (sum of l largest coordinates in absolute value), which enjoys various closure properties. Our chief contribution is a framework for designing approximation algorithms for stochastic minimum-norm optimization, which has two key components: (i) A reduction showing that one can control the expected f-norm by simultaneously controlling a (small) collection of expected Top-l norms; and (ii) Showing how to tackle the minimization of a single expected Top-l-norm by leveraging techniques used to deal with minimizing the expected maximum, circumventing the difficulties posed by the non-separable nature of Top-l norms. We apply our framework to obtain strong approximation guarantees for two concrete problem settings: (1) stochastic load balancing, wherein jobs have random processing times and the induced cost vector is the machine-load vector; and (2) stochastic spanning tree, where edges have stochastic weights and the cost vector consists of the edge-weight variables of edges in the spanning tree returned. This is joint work with Sharat Ibrahimpur.

In submodular k-partition, the input is a non-negative submodular function f defined over a finite ground set V (given by an evaluation oracle) along with a positive integer k and the goal is to partition the ground set V into k non-empty parts $V_1, V_2, \ldots , V_k$ in order to minimize $\sum_{i=1}^k f(V_i)$. Submodular k-partition generalizes partitioning problems over several interesting structures including graphs, hypergraphs, and matrices. Submodular k-partition is NP-hard and is O(k)-approximable. In this talk, I will focus on the approximability of submodular k-partition for three subfamilies of submodular functions – namely symmetric, monotone, and posimodular submodular functions. I will present the principal partition sequence based algorithm for submodular k-partition designed by Narayanan, Roy, and Patkar (1996) and sketch its approximation factor analysis for these three subfamilies of submodular functions. Based on joint work with Weihang Wang.

Motivated by cloud computing applications, we study the problem of how to deploy new hardware subject to power and robustness constraints. We have identical devices with capacity constraints. Demands come one-by-one and, to be robust against a device failure, need to be assigned to a pair of devices. When a device fails (in a failover scenario), each demand assigned to it is rerouted to its paired device (which may now run at increased capacity). The goal is to assign demands to the devices to maximize the total utilization subject to both the normal capacity constraints as well as these novel failover constraints. These latter constraints introduce new decision tradeoffs not present in classic assignment problems such as Multiple Knapsack and AdWords. We present algorithms for both the worst case and stochastic model, where demands come i.i.d. from an unknown distribution. The latter requires a combination of different techniques, including a configuration LP with a non-trivial post-processing step and an online monotone matching procedure introduced by Rhee and Talagrand. This is a joint work with Konstantina Mellou and Marco Molinaro.

Lunch is served daily between 11:30am and 1:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building.

A buffet dinner is served daily between 5:30pm and 7:30pm in Vistas Dining Room, 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 will examine the notion of explainable k-means and k-medians clustering recently introduced by Dasgupta, Frost, Moshkovitz, and Rashtchian. I will give an overview of the recent results and then show a simple O(log k) competitive algorithm for the explainable k-medians problem. Based on joint works with Liren Shan (Northwestern, TTIC).

For a constraint satisfaction problem (CSP), a robust satisfaction algorithm is one that outputs an assignment satisfying most of the constraints on instances that are near-satisfiable. It is known that the CSPs that admit efficient robust satisfaction algorithms are precisely those of bounded width, i.e., CSPs whose satisfiability can be checked by a simple local consistency algorithm (eg., 2-SAT or Horn-SAT in the Boolean case). While the exact satisfiability of a bounded width CSP can be checked by combinatorial algorithms, the robust algorithm is based on rounding a canonical semidefinite programming (SDP) relaxation. In this work, we initiate the study of robust satisfaction algorithms for promise CSPs, which are a vast generalization of CSPs that have received much attention recently. The motivation is to extend the theory beyond CSPs, as well as to better understand the power of SDPs. We present robust SDP rounding algorithms under some general conditions, namely the existence of particular high-dimensional Boolean symmetries known as majority or alternating threshold polymorphisms. On the hardness front, we prove that the lack of such polymorphisms makes the promise CSP hard for all pairs of symmetric Boolean predicates. Our method involves a novel method to argue SDP gaps via the absence of certain colorings of the sphere, with connections to sphere Ramsey theory. Joint work with Josh Brakensiek and Sai Sandeep.

5-day workshop participants are welcome to use BIRS facilities (TCPL ) until 3 pm on Friday, although participants are still required to checkout of the guest rooms by 11AM.

Cheeger's inequality is a fundamental result in spectral graph theory connecting the edge conductance of an undirected graph to the second eigenvalue of its Laplacian matrix. In this talk, we will present a unifying approach to prove Cheeger-type inequalities in more general settings using the concept of reweighted eigenvalues. This provides a new spectral theory for vertex expansion, for directed graphs, and for hypergraphs, that is much closer to the spectral theory for undirected graphs that were previously known. An interesting consequence is a characterization of the fastest mixing time of a directed graph by its vertex expansion. Joint work with Tsz Chiu Kwok, Kam Chuen Tung, and Robert Wang.