In the traditional frameworks for optimization under uncertainty, an algorithm has to accept the incompleteness of input data. Clearly, more information or even knowing the exact data would allow for significantly better solutions. How much more information suffices for obtaining a certain solution quality? Which information shall be retrieved? Explorable uncertainty is a framework in which parts of the input data are initially unknown, but can be obtained at a certain cost using queries. An algorithm can make queries until it has obtained sufficient information to solve a given problem. The challenge lies in balancing the cost for querying and the impact on the solution quality. In this talk, I will give an overview on the field of explorable uncertainty with a focus on combinatorial optimization problems. I will include problems such as finding a minimum spanning tree in a graph of uncertain edge cost, finding the minimal elements in intersecting sets, and finding a set of minimum total value. The latter can be seen as a subproblem of more complex problem such as a solving a knapsack or matching problem under explorable uncertainty. I will discuss an adversarial online model and recent advances on a stochastic variant.

- Karthik Chanrasekaran
- Omar El Housni
- Dion Gijswijt
- Dorothee Henke

We study the optimal provision of information for two natural performance measures of queuing systems: throughput and makespan. A set of parallel links (queues) is equipped with deterministic capacities and stochastic travel times where the latter depend on a realized scenario. A continuum of flow particles (users) arrives at the system at a constant rate. A system operator knows the realization of the scenario and may (partially) reveal this information via a public signaling scheme to the flow particles. Upon arrival, the flow particles observe the signal issued by the system operator, form an updated belief about the realized scenario, and decide on a link to use. Inflow into a link exceeding the link’s capacity builds up in a queue that increases the travel time on the link. Dynamic inflow rates are in a Bayesian dynamic equilibrium when the expected travel time along all links with positive inflow is equal at every point in time. For a given time horizon T , the throughput induced by a signaling scheme is the total volume of flow that leaves the links in the interval [0, T ]. We show that the public signaling scheme that maximizes the throughput may involve irrational numbers and provide an additive polynomial time approximation scheme (PTAS) that approximates the optimal throughput by an arbitrary additive constant ? > 0. The algorithm solves a Langrangian dual of the signaling problem with the Ellipsoid method whose separation oracle is implemented by a cell decomposition technique. We also provide a multiplicative fully polynomial time approximation scheme (FPTAS) that does not rely on strong duality and, thus, allows to compute also the optimal signals. It uses a different cell decomposition technique together with a piece-wise convex under-estimator of the optimal value function. Finally, we consider the makespan of a Bayesian dynamic equilibrium which is defined as the last point in time when a total given value of flow leaves the system. Using a variational inequality argument, we show that full information revelation is a public signaling scheme that minimizes the makespan. This is joint work with Max Klimm, Philipp Warode, and Theresa Ziemke.

We analyze the formal complexity question of conducting sensitivity analysis for MBQPs: We show that even if the optimal solution of a given MBQP is known, it is NP-hard to achieve a two-sided (a, b)-approximation of the absolute value of the change in objective function value with respect to changes in rhs (for any fixed value of 0

Symmetry handling inequalities are an appealing and popular tool for handling symmetries in IPs. Despite their practical application, little is known about their interaction with optimization problems. In this talk we'll investigate the impact of adding Schreier-Sims (SST) cuts, a recently introduced family of symmetry handling inequalities, from a computational and polyhedral complexity perspective. First, we observe that SST cuts do not increase the computational complexity of solving an (integral) linear optimization problem over any polytope P. However, separating the integer hull of P enriched by SST cuts can be NP-hard, even if P is integral and has a compact formulation. We study this phenomenon more in-depth for the stable set problem, particularly for subclasses of perfect graphs. In particular, we observe that the separation problem is still NP-hard after adding a generic set of SST cuts for trivially perfect graphs. Our main contribution is identifying a specific class of SST cuts, that keeps the separation problem polynomial and a complete linear description of the integer hull. Our theoretical results are complemented with computational experiments. This is joint work with Christopher Hojny and Marc Pfetsch.

Using the recently proposed maximal quadratic-free sets and the well-known monoidal strengthening procedure, we show how to improve intersection cuts for quadratically-constrained optimization problems by exploiting integrality requirements. We provide an explicit construction that allows an efficient implementation of the strengthened cuts along with computational results showing their improvements over the standard intersection cuts. We also show that, in our setting, there is unique lifting which implies that our strengthening procedure is generating the best possible cut coefficients for the integer variables.

- Christopher Hojny
- Kirill Kukharenko
- Stefan Lendl
- Jeff Linderoth
- Alantha Newman
- Christian Nöbel
- Joseph Paat

We show that given m disjoint chains in the Boolean lattice, we can create m disjoint skipless chains that cover the same elements (where we call a chain skipless if any two consecutive elements differ in size by exactly one). By using this result we are able to answer two conjectures about the asymptotics of induced saturation numbers for the antichain, which are defined as follows. For positive integers k and n, a family F of subsets of {1,...,n} is k-antichain saturated if it does not contain an antichain of size k (as induced subposet), but adding any set to F creates an antichain of size k. We use sat*(n,k) to denote the smallest size of such a family. With more work we pinpoint the exact value of sat*(n, k), for all k and sufficiently large n. Previously, exact values for sat*(n,k) were only known for k up to 6. We also show that for any poset P, its induced saturation number (which is defined similar as for the antichain) grows at most polynomially: sat*(n, P)=O(n^c), where c <= |P|^2/4+1. This is based on joint works with Paul Bastide, Maria-Romina Ivan, Hugo Jacob and Tom Johnston.

- Axel Parmentier
- Ulrich Pferschy
- Marc Pfetsch
- Diane Puges
- Guido Schäfer
- Frits Spieksma
- Marc Uetz

In this talk, we explore novel aspects of k-median and k-means clustering, which are central optimization problems with many applications in data analysis and machine learning. We focus on what makes a clustering explainable, and we present simple algorithms that have strong theoretical guarantees. We complement these findings with several interesting related directions and open questions. This is based on joint works with Buddhima Gamlath, Xinrui jia, Adam Polak and Anupam Gupta, Madhusudhan Reddy Pittu, Rachel Yuan.

- Barahona Francisco
- Bishnoi Anurag
- Dadush Daniel
- Held Stephan
- Klimm Max
- Wiegele Angelika

The joint replenishment problem (JRP) is a classical inventory management problem. We consider a natural generalization with outliers, where we are allowed to reject (that is, to not service) a subset of demand points. In this paper, we are motivated by issues of fairness - if we do not serve all of the demands, we wish to "spread out the pain" in a balanced way among customers, communities, or any specified market segmentation. One approach is to constrain the rejections allowed, and to have separate bounds for each given customer. In our most general setting, we consider a set of C features, where each demand point has an associated rejection cost for each feature, and we have a given hard constraint on the allowed rejection cost incurred in total for each feature. This generalizes a model of fairness introduced in earlier work on the Colorful k-Center problem in which (analogously) each demand point has a given color, and we bound the number of rejections of each color class. We give the first constant approximation algorithms for the fairness-constrained JRP with a constant number of features (or colors); specifically, we give a 2.86-approximation algorithm in this case. Even for the special case in which we bound the total (weighted) number of outliers, this performance guarantee improves upon bounds previously known for this case. Our approach is an LP-based algorithm that splits the instance into two subinstances. One is solved by a novel iterative rounding approach and the other by pipage-based rounding. The standard LP relaxation has an unbounded integrality gap, and hence another key element of our algorithm is to strengthen the relaxation by correctly guessing key attributes of the optimal solution, which are sufficiently concise, so that we can enumerate over all possible guesses in polynomial time - albeit exponential in C, the number of features. This is joint work with Varun Suriyanarayana, Varun Sivashankar, and Siddharth Gollapudi.

Correlation clustering is a natural model arising from community detection problems. A complete graph is given with each edge labeled as either positive or negative; two vertices are connected by a positive edge when they are “similar" and want to being clustered together, while a negative edge indicates vertices that are “dissimilar" and want to be in different clusters. The goal is to find a clustering that minimizes an objective capturing the edges’ disagreements with respect to the clustering. In this talk, we focus on objectives that minimize the $\ell_p$-norm of the disagreement vector, which is a well-studied class of objective. Our work provides the first purely combinatorial constant factor approximation algorithms for these problems. Additionally, we provide an algorithm that produces a single clustering solution that is simultaneously constant approximate for all $\ell_p$-norms of the disagreement vector. This proves that minimal sacrifice is needed in order to optimize different local norms. The combinatorial nature of our techniques lend to significant run-time improvements, with empirical results showing that our algorithms scale to larger networks that were effectively intractable for previous algorithms.

One of the most popular clustering algorithms is the celebrated D^a seeding algorithm (also know as k-means++ when a = 2) by Arthur and Vassilvitskii (2007), who showed that it guarantees in expectation an O(2^(2a)·log k)-approximate solution to the (k,a)-means cost (where euclidean distances are raised to the power a) for any a > 1. In this talk, I will present new results on the performance of D^a seeding algorithm for a>2 with respect to the standard (k,2)-means cost. We identify 3 critical parameters and show that if those parameters are well-behaved then the D^a seeding algorithm for a>2 can guarantee much better than an O(log k)-approximation. For instance, if the dataset is obtained by a mixture of k Gaussians distributions which have the same variance (up to a constant-factor) then D^a seeding gives a constant-factor approximation if there are a constant number of mixing weights, and an O(a^3·log(k)^{2/a})-approximation for arbitrary mixing weights. This is a joint work with Sai Ganesh Nagarajan and Ola Svensson.

Recent improvements within adder optimization could be achieved by optimizing the AND-trees occurring within the constructed circuits. The overlap of such trees and its potential for pure size optimization has not been taken into account though. Motivated by this, we examine the fundamental problem of minimizing the size of a circuit for multiple AND-functions on intersecting variable sets. Our formulation generalizes the overlapping AND-trees within adder optimization but is in NP, in contrast to general Boolean circuit optimization which is in $\Sigma_2^p$ and not in NP unless P=NP. While restructuring the AND- or XOR-trees simultaneously, we optimize the total number of gates needed for all functions to be computed. We show that this problem is APX-hard already for small functions and present approximation algorithms for the case in which the Boolean functions depend on at most 3 or 4 variables each, achieving guarantees of 4/3 and 1.9 respectively. To conclude, we give an approximation algorithm with guarantee 2k/3 for general symmetric Boolean functions with up to k inputs. To achieve these results, the key technique is to determine how much overlap among the variable sets makes tree construction cheap and how few makes the optimum solution large.

- Bansal Ishan
- Friggstad Zachary
- Fukasawa Ricardo
- Koster Arie
- Matuschke Jannik
- Molero Cristina
- Mömke Tobias
- Skutella Martin

When someone is denied a job, offered a different price for the same goods or services, denied bail or declined a loan, intent to discriminate is often not the case. The decision system applies the same data and rules to all and yet has a disproportionate effect on a protected class, i.e., individuals protected by law from discrimination based on sex, race, age, etc. The causes of such disparate impact in machine learning and optimization are many, but two prominent ones that my work focuses on are: (i) Biases in Data and (ii) Competing objectives. The first entails reliance on observed data that inherently embeds socio-economic and historical practices, e.g., test scores are known to be underestimated for students in stereotyped groups and low-income families, leading to discriminatory outcomes. The latter set of problems entails trade-offs with utilitarian objectives, equity, efficiency, and learnability. I will discuss some new and old combinatorial optimization problems for tackling biases in data and competing objectives, for applications ranging from hiring, admissions, facility location, and demand learning.

Elevator pitch speakers:
- Sweering Michelle
- Walter Matthias


Abstract of Neil's talk:

We consider a dynamic model of traffic that has received a lot of attention in the past few years. Infinitesimally small agents aim to travel from a source to a destination as quickly as possible. Flow patterns vary over time, and congestion effects are modeled via queues, which form based on the deterministic queueing model whenever the inflow into a link exceeds its capacity.

Are equilibria in this model meaningful as a prediction of traffic behavior? For this to be the case, a certain notion of stability under ongoing perturbations is needed. Real traffic consists of discrete, atomic "packets", rather than being a continuous flow of non-atomic agents. Users may not choose an absolutely quickest route available, if there are multiple routes with very similar travel times. We would hope that in both these situations - a discrete packet model, with packet size going to 0, and epsilon-equilibria, with epsilon going to 0 - equilibria converge to dynamic equilibria in the flow over time model. We give a positive answer to these questions for single-commodity instances.

Joint work with Leon Sering and Laura Vargas Koch. (Appeared at FOCS 2023.)

It is very well-known that every graph with average degree at least 2 must contain a cycle. This talk concerns a rainbow version of this classical result: What average degree is needed in a properly edge-coloured n-vertex graph in order to guarantee a rainbow cycle, i.e. a cycle in which every colour appears at most once? We prove an essentially tight bound for this problem, showing that average degree C log n log log n suffices (for some sufficiently large absolute constant C). This is tight up to the log log n factor, and improves upon previous bounds of Keevash-Mubayi-Sudakov-Verstraëte, Das-Lee-Sudakov, Janzer, Tomon, Janzer-Sudakov, and Kim-Lee-Liu-Tran. Joint work with Noga Alon, Matija Buci?, Dmitrii Zakharov, and Or Zamir.

We study the problem of chasing positive bodies in \ell_1: given a sequence of bodies K_t\subset R^n revealed online, where each K_t is defined by a mixed packing-covering linear program, the goal is to (approximately) maintain a point x_t \in K_t such that \sum_t \|x_t - x_{t-1}\|_1 is minimized. This captures the fully-dynamic low-recourse variant of any problem that can be expressed as a mixed packing-covering linear program and thus also the fractional version of many central problems in dynamic algorithms such as set cover, load balancing, hyperedge orientation, minimum spanning tree, and matching. We give an O(\log n)-competitive algorithm for this problem. This bypasses and improves exponentially over the lower bound of \sqrt{n} known for general convex bodies. Our algorithm is based on iterated information projections, and, in contrast to general convex body chasing algorithms, is entirely memoryless. We also show how to round our solution dynamically to obtain the first fully dynamic algorithms with {competitive recourse} for all the stated problems above; i.e. their recourse is less than the recourse of every other algorithm on every update sequence, up to polylogarithmic factors. This is a significantly stronger notion than the notion of {absolute recourse} in the dynamic algorithms literature.

In this talk, we focus on mixed integer nonlinear problems with piecewise convex inequalities. We generalize the classic formulation for piecewise linear functions to the case of piecewise convex ones and strengthen them through perspective reformulation. Moreover, we compare the different formulations and we show that they are not equivalent, contrarily to what has been shown in the literature for the piecewise linear formulations.

We give a strongly polynomial algorithm for minimum cost generalized flow, and hence for optimizing any linear program with at most two non-zero entries per row, or at most two non-zero entries per column. Primal and dual feasibility were shown by Megiddo (SICOMP '83) and Végh (MOR '17) respectively. Our result can be viewed as progress towards understanding whether all linear programs can be solved in strongly polynomial time, also referred to as Smale's 9th problem. Our approach is based on the recent primal-dual interior point method (IPM) due to Allamigeon, Dadush, Loho, Natura and Végh (FOCS '22). The number of iterations needed by the IPM is bounded, up to a polynomial factor in the number of inequalities, by the straight line complexity of the central path. Roughly speaking, this is the minimum number of pieces of any piecewise linear curve that multiplicatively approximates the central path. As our main contribution, we show that the straight line complexity of any minimum cost generalized flow instance is polynomial in the number of arcs and vertices. By applying a reduction of Hochbaum (ORL '04), the same bound applies to any linear program with at most two non-zeros per column or per row. To be able to run the IPM, one requires a suitable initial point. For this purpose, we develop a novel multistage approach, where each stage can be solved in strongly polynomial time given the result of the previous stage. Beyond this, substantial work is needed to ensure that the bit complexity of each iterate remains bounded during the execution of the algorithm. For this purpose, we show that one can maintain a representation of the iterates as a low complexity convex combination of vertices. Our approach is black-box and can be applied to any log-barrier path following method.

Robust optimization provides a mathematical framework for modeling and solving decision-making problems under worst-case uncertainty. This work addresses two-stage robust optimization (2RO) problems (also called adjustable robust optimization), wherein first-stage and second-stage decisions are made before and after uncertainty is realized, respectively. This results in a nested min-max-min optimization problem which is extremely challenging computationally, especially when the decisions are discrete. We propose Neur2RO, an efficient machine learning-driven instantiation of column-and-constraint generation (CCG), a classical iterative algorithm for 2RO. Specifically, we learn to estimate the value function of the second-stage problem via a novel neural network architecture that is easy to optimize over by design. Embedding our neural network into CCG yields high-quality solutions quickly as evidenced by experiments on two 2RO benchmarks, knapsack and capital budgeting. For knapsack, Neur2RO finds solutions that are within roughly of the best-known values in a few seconds compared to the three hours of the state-of-the-art exact branch-and-price algorithm; for larger and more complex instances, Neur2RO finds even better solutions. For capital budgeting, Neur2RO outperforms three variants of the k-adaptability algorithm, particularly on the largest instances, with a 5 to 10-fold reduction in solution time.

Two-stage stochastic programs (2SPs) with binary recourse are challenging to solve and efficient solution methods for such problems have been limited. Leveraging the combinatorial nature of binary programs, we convexify the second-stage problems using binary decision diagrams (BDDs) to make the problem amenable to Benders decomposition algorithm. More specifically, we first generalize an existing BDD-based approach to allow settings where logical expressions of the first-stage solutions enforce constraints in the second stage, making it applicable to a wide array of problems. We also propose a complementary problem where second-stage objective coefficients are impacted by logical expressions of the first-stage decisions, and develop a distinct BDD-based algorithm to solve this novel problem class. In the two alternative settings, while convexifying the second-stage problems, we parametrize either the arc costs or capacities of the BDDs with first-stage solutions. We further extend this work by incorporating conditional value-at-risk and we propose, to our knowledge, the first decomposition method for 2SPs with binary recourse and a risk measure. We apply these methods to a novel stochastic dominating set problem and present numerical results to demonstrate the effectiveness of the proposed methods.

In 1971, Balas introduced intersection cuts as a method for generating cutting planes in integer optimization. These cuts are derived from convex S-free sets, and inclusion-wise maximal S-free sets yield the strongest intersection cuts. When S is a lattice, maximal S-free sets are well-studied from theoretical and computational standpoints. In this talk, we focus on the case when S is defined by a general quadratic inequality and show how to construct basic maximal quadratic-free sets. Additionally, we explore how to generalize the basic procedure to construct a plethora of new maximal quadratic-free sets for homogeneous quadratics. We will finalize with open questions on this topic. Joint work with Antonia Chmiela, Joseph Paat, and Felipe Serrano.

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 \pedges across parts plus the number of the \medges within parts. Recently, Cohen-Addad, Lee and Newman [CLN22] 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 [CMSY15]. 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 {\em correlated rounding} used by [CLN22]. This additional power simplifies the previous algorithm and analysis. More importantly, it enables a new {\em set-based rounding} that complements the previous roundings. A combination of these two rounding algorithms yields the improved bound. Joint work with Euiwoong Lee, Shi Li, Alantha Newman

Adaptive submodularity is a fundamental concept in stochastic optimization, with numerous applications such as sensor placement, hypothesis identification and viral marketing. We consider the problem of minimum cost cover of adaptive-submodular functions, and provide a 4(1 + ln Q)-approximation algorithm, where Q is the goal value. In fact, we consider a significantly more general objective of minimizing the p-th moment of the coverage cost, and show that our algorithm simultaneously achieves a (p+1)^{p+1} (1+ln Q)^p approximation guarantee for all p. All our approximation ratios are best possible up to (small) constant factors. Moreover, our results also extend to the setting where one wants to cover multiple adaptive-submodular functions.

The robust minimum cost flow problem under consistent flow constraints (RobMCF?) is a new extension of the minimum cost flow (MCF) problem motivated by an appointment scheduling problem for general practitioners (GPs). In the RobMCF? problem, we consider demand and supply that are subject to uncertainty. For all demand realizations, however, we require that the flow value on an arc needs to be equal if it is included in the predetermined arc set given. The objective is to find feasible flows that satisfy the equal flow requirements while minimizing the maximum occurring cost among all demand realizations. In the case of a finite discrete set of scenarios, we derive structural results which point out the differences with the polynomial time solvable MCF problem in networks with integral demands, supplies, and capacities. We show that the RobMCF? problem is strongly NP-hard on acyclic digraphs. However, for some special case on series-parallel digraphs we can solve the RobMCF? problem in polynomial time. Finally, we shortly present how this model can improve an appointment scheduling system for GPs.

We devise constant-factor approximation algorithms for finding as many disjoint cycles as possible from a certain family of cycles in a given planar or bounded-genus graph. Here disjoint can mean vertex-disjoint or edge-disjoint, and the graph can be undirected or directed. The family of cycles under consideration must satisfy two properties: it must be uncrossable and allow for an oracle access that finds a weight-minimal cycle in that family for given nonnegative edge weights or (in planar graphs) the union of all remaining cycles in that family after deleting a given subset of edges. Our setting generalizes many problems that were studied separately in the past. For example, three families that satisfy the above properties are (i) all cycles in a directed or undirected graph, (ii) all odd cycles in an undirected graph, and (iii) all cycles in an undirected graph that contain precisely one demand edge, where the demand edges form a subset of the edge set. The latter family (iii) corresponds to the classical disjoint paths problem in fully planar and bounded-genus instances. While constant-factor approximation algorithms were known for edge-disjoint paths in such instances, we improve the constant in the planar case and obtain the first such algorithms for vertex-disjoint paths. We also obtain approximate min-max theorems of the Erd\H{o}s--P\'osa type. For example, the minimum feedback vertex set in a planar digraph is at most 12 times the maximum number of vertex-disjoint cycles. Most of this talk is based on joint work with Niklas Schlomberg and Hanjo Thiele, published in SODA 2023.

Finding a quantum optimization algorithm with an end-to-end speedup, compared to the fastest known classical algorithm for the same problem, would be great. Finding *two* would be even better. We discuss two recent such algorithms: one for the SDP relaxation of MaxCut, and one for linear programs that are not too dense. The first algorithm is based on mirror descent, and also yields a faster classical algorithm for the same problem. The second one uses a quantum mechanical simulation of the central path equations. Although yet-undiscovered faster classical algorithms are not ruled out, these algorithms provide credible evidence that quantum computers could, in theory, be useful to solve the continuous relaxation of famous combinatorial problems. Based on https://arxiv.org/abs/2301.04237 and https://arxiv.org/abs/2311.03977

We revisit the a priori TSP (with independent activation) and prove stronger approximation guarantees than were previously known. In the a priori TSP, we are given a metric space (V, c) and an activation probability p(v) for each customer v ? 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 master route solution, consisting of a TSP tour for S and two edges connecting every customer v ? V \ 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.

Capacitated network bargaining games are popular combinatorial games that involve the structure of matchings in graphs. We show that it is always possible to stabilize unweighted instances of this problem (that is, ensure that they admit a stable outcome) via capacity-reduction and edge-removal operations, without decreasing the total value that the players can get. Furthermore, for general weighted instances, we show that computing a minimum amount of vertex-capacity to reduce to make an instance stable is a polynomial-time solvable problem. We then exploit this to give approximation results for the NP-hard problem of stabilizing a graph via edge-removal operations. Our work extends and generalizes previous results in the literature that dealt with an uncapacitated version of the problem, using several new arguments. In particular, while previous results mainly used combinatorial techniques, we here rely on polyhedral arguments and, more specifically, on the notion of circuits of a polytope. This is joint work with Lucy Verberk

This is joint work with Nathan Klein and Martin Nägele. Prize-Collecting TSP is a variant of the traveling salesperson problem where one may drop vertices from the tour at the cost of vertex-dependent penalties. The quality of a solution is then measured by adding the length of the tour and the sum of all penalties of vertices that are not visited. We present a polynomial-time approximation algorithm with an approximation guarantee slightly below 1.6, where the guarantee is with respect to the natural linear programming relaxation of the problem. This improves upon the previous best-known approximation ratio of 1.774. Our approach is based on a known decomposition for solutions of this linear relaxation into rooted trees. Our algorithm takes a tree from this decomposition and then performs a pruning step before doing parity correction on the remainder. Using a simple analysis, we bound the approximation guarantee of the proposed algorithm by (1+?5)/2?1.618, the golden ratio. With some additional technical care we further improve it to 1.599.

The weighted $k$-Set Packing problem is defined as follows: As input, we are given a collection $\mathcal{S}$ of sets, each of cardinality at most $k$, and positive weights $w:\mathcal{S}\rightarrow\mathbb{R}_{>0}$. The task is to compute a sub-collection $A\subseteq \mathcal{S}$ such that the sets in $A$ are pairwise disjoint, and the total weight of $A$ is maximum. The case $k=2$ is equivalent to the Maximum Weight Matching problem. For $k\geq 3$, already the special case of unit weights, the unweighted $k$-Set Packing problem, is NP-hard. The technique that has proven most successful in designing approximation algorithms for both the unweighted and the weighted $k$-Set Packing problem is local search. For the unweighted problem, the state-of-the-art is a polynomial-time $\frac{k+1}{3}+\epsilon$-approximation by F\"urer and Yu that takes into account certain local improvements of up to logarithmic size. For general weights, we recently showed that by considering a special class of local improvements of logarithmically bounded size, we can obtain a polynomial-time $\frac{k+\epsilon_k}{2}$-approximation, where $\lim_{k\rightarrow\infty}\epsilon_k =0$. We further proved that this result is asymptotically best possible: For general weights, one cannot achieve a better guarantee than $\frac{k}{2}$ by only considering local improvements of logarithmically bounded size. At a first glance, this seems to conclude the story of local improvement algorithms for the weighted $k$-Set Packing problem. However, in this talk we show how to employ a black box algorithm for the unweighted $k$-Set Packing problem to generate local improvements of super-logarithmic size and obtain a polynomial-time $(\frac{k}{2}-\Omega(k))$-approximation algorithm for weighted $k$-Set Packing. Our techniques further allow us to establish a general connection between the approximation guarantees achievable for unit and general weights. This result has been published in the proceedings of SODA 2023.

In this talk, we present a computational overview on computing Nash equilibria in integer programming games (IPGs), that is, how to compute solutions for a class of noncooperative and nonconvex games where each player solves a mixed-integer optimization problem. IPGs are a broad class of games extending the modeling power of mixed-integer optimization to multiagent settings. This class of games includes, for instance, any finite game and any multiagent extension of traditional combinatorial optimization problems. After providing some background motivation and context of applications, we systematically review and classify the state-of-the-art algorithms to compute Nash equilibria. We propose an essential taxonomy of the algorithmic ingredients needed to compute equilib- ria, and we describe the theoretical and practical challenges associated with equilibria computation. Finally, we quantitatively and qualitatively compare a sequential Stackelberg game with a simultaneous IPG to highlight the different properties of their solutions.

We consider cost allocation for set covering problems. We allocate as much cost to the elements (players) as possible without violating the group rationality condition (no subset of players pays more than covering this subset would cost), and so that the excess vector is lexicographically maximized. This is identical to the well-known nucleolus if the core of the corresponding cooperative game is nonempty, i.e., if some optimum fractional cover is integral. In general, we call this the happy nucleolus. Like for the nucleolus, the excess vector contains an entry for every subset of players, not only for the sets in the given set covering instance. Moreover, it is NP-hard to compute a single entry because this requires solving a set covering problem. Nevertheless, we give an explicit family of at most mn subsets, each with a trivial cover (by a single set), such that the happy nucleolus is always completely determined by this proxy excess vector; here m and n denote the number of sets and the number of players in our set covering instance. We show that this is the unique minimal such family in a natural sense. While computing the nucleolus for set covering is NP-hard, our results imply that the happy nucleolus can be computed in polynomial time.

We study the budget aggregation problem in which a set of strategic voters must split a finite divisible resource (such as money or time) among a set of competing projects. Our goal is twofold: We seek truthful mechanisms that provide fairness guarantees to the projects. For the first objective, we focus on the class of moving phantom mechanisms [Freeman et al., 2021], which are -- to this day -- essentially the only known truthful mechanisms in this setting. For project fairness, we consider the mean division as a fair baseline, and bound the maximum difference between the funding received by any project and this baseline. We propose a novel and simple moving phantom mechanism that provides optimal project fairness guarantees. As a corollary of our results, we show that our new mechanism minimizes the l1 distance to the mean for three projects and gives the first non-trivial bounds on this quantity for more than three projects. This is joint work with Rupert Freeman.

We consider ascending auctions for finding Walrasian equilibria in markets with indivisible items and gross substitutes valuation functions. Each price increase step in the auction algorithm requires finding an inclusion-wise minimal maximal overdemanded set at the current prices. This can be formulated as a submodular function minimization problem. We observe that minimizing this submodular function corresponds to a polymatroid sum problem, and using this viewpoint, we give a fast and simple push-relabel algorithm for finding the minimal maximal overdemanded set. This improves on the previously best running time of Murota, Shioura and Yang (ISAAC 2013). Our algorithm is an adaptation of the push-relabel framework by Frank and Miklós (JJIAM 2012) to the particular setting. We obtain a further improvement for the special case of unit-supplies. Furthermore, we show that for gross substitutes valuations, the component-wise minimal competitive prices are the same as the minimal Walrasian prices. This enables us to derive monotonicity properties of the Walrasian prices. Namely, we show that the minimal Walrasian prices can only increase if supply decreases, or demand increases. This is joint Work with Britta Peis, Niklas Rieken, Laura Vargas Koch and Lázló A. Végh.

The seminal papers of Edmonds, Nash-Williams and Tutte have laid the foundations of the theories of packing arborescences and packing trees. The directed version has been extensively investigated, resulting in a great number of generalizations. In contrast, the undirected version has been marginally considered. The aim of this talk is to further develop the theory of packing trees and forests. We present a broad extension of an already generic theorem on packing spanning branchings of Bérczi and Frank, as well as its undirected counterpart which is our main result. This is a joint work with Pierre Hoppenot and Mathis Martin.

An alpha-approximate universal Steiner tree (UST) of a graph G is a spanning tree T such that, for any vertex terminal subset S, the minimal subtree of T connecting S is within an alpha factor of the cost of the cheapest Steiner tree in G connecting S. Alpha-approximate USTs immediately give alpha-approximations for well-studied variants of Steiner tree such as online or oblivious Steiner tree. Sub-linear-approximate USTs are known but neither the existence of nor poly-time algorithms for computing poly-logarithmic-approximate USTs were previously known. In this talk, I will discuss the first construction of poly-logarithmic USTs. The result is based on new constructions of poly-logarithmic-quality graph hierarchies called strong sparse partitions which may be interesting in their own right. Roughly, strong sparse partitions provide deterministic guarantees on how often balls of particular radii are cut. Joint work @FOCS23 with Costas Busch, Da Qi Chen, Arnold Filtser, Daniel Hathcock and Rajmohan Rajaraman.

Sample average approximation (SAA) is a technique to obtain solutions and bounds for stochastic programming problems. When applying SAA, it is often useful to solve multiple SAA problems with different samples, to obtain a confidence interval on the optimal value, or to obtain a better solution. We study techniques to accelerate the solution of this sequence of SAA problems, when solving them via Benders decomposition. We exploit similarities in the problem structure, as the problems just differ in the realizations of the random samples. Our extensive computational experiments demonstrate it is possible to significantly reduce the total time required to solve a sequence of SAA problems. We present some theoretical results that provide insight into the algorithm’s performance.

A (binary) cyclic transversal of a configuration of n subsets („blocks“) of the d-dimensional vector space over the field with two elements is a selection of exactly one vector from each block for which the sum of the selected vectors equals zero. We introduce the cyclic transversal polytope („CTP“) associated with such a block configuration as the convex hull of the incidence vectors of all its cyclic transversals. In the first part of the talk we discuss the modeling power of the concept. For instance, we demonstrate how cut polytopes and stable set polytopes are isomorphic to CTP’s and discuss a universality theorem stating that many other 0/1-polytopes (e.g., TSP-polytopes) are projections of CTP’s associated with block configurations of small sizes. In the second part we introduce the class of lifted odd set („LOS“) inequalities, which, e.g., generalize the odd-hole inequalities for stable set polytopes. We show that the LOS-inequalities provide complete descriptions of all CTP’s with d=2. The talk concludes with describing a natural relaxation hierarchy for CTP’s that might be interesting in the light of the modeling power of CTP’s. The main part of the talk ist based on joint work with Jonas Frede (OVGU Magdeburg) and Maximilian Merkert (TU Braunschweig).

We address computation of the degrees of minors of noncommutative symbolic matrix of form \[ A[c] := \sum_{k=1}^m A_k t^{c_k} x_k, \] where $A_k$ is a matrix over field $\KK$, $x_i$ are noncommutative variables, $t$ is a commuting variable specifying the degree, and $c_i$ are integer costs. This problem extends noncommutative Edmonds' problem (Ivanyos et al. 2017), and can formulate various combinatorial optimization problems. Extending the study by Hirai 2018, and Hirai, Ikeda 2022, we provide novel duality theorems and polyhedral characterization for the maximum degree of minors of $A[c]$ of all sizes, and devise a strongly polynomial time algorithm for computing them. This algorithm is an algebraization of the classical Hungarian method for bipartite matching and weight splitting algorithm for linear matroid intersection. As applications, we provide strongly polynomial-time algorithms for weighted fractional linear matroid matching and linear optimization over rank-2 Brascamp-Lieb polytopes.

In 2000, Gerard Cornuejols, Bertrand Guenin and Francois Margot conjectured that ideal minimally nonpacking clutters always have covering number 2, and they gave an infinite class of such clutters. We revisit this conjecture, review what we know, present new infinite classes as well as new open problems. This is joint work with Ahmad Abdi and Siyue Liu.

Contention resolution schemes (or CR schemes), introduced by Chekuri, Vondrak and Zenklusen, are a class of randomized rounding algorithms for converting a fractional solution to a relaxation for a down-closed constraint family into an integer solution. A CR scheme takes a fractional point x in a relaxation polytope, rounds each coordinate xi independently to get a possibly non-feasible set, and then drops some elements in order to satisfy the constraints. Intuitively, a contention resolution scheme is c-balanced if every element i is selected with probability at least $c x_i$. It is known that general matroids admit a $(1?1/e)$-balanced CR scheme, and that this is (asymptotically) optimal. This is in particular true for the special case of uniform matroids of rank one. In this work, we provide a simple and explicit monotone CR scheme for uniform matroids of rank k on n elements with a balancedness of $1 - \binom{n}{k}\:\left(1-\frac{k}{n}\right)^{n+1-k}\:\left(\frac{k}{n}\right)^k$, and show that this is optimal. As n grows, this expression converges from above to $1 - e^{-k}k^k/k!$. While this asymptotic bound can be obtained by combining previously known results, these require defining an exponential-sized linear program, as well as using random sampling and the ellipsoid algorithm. Our procedure, on the other hand, has the advantage of being simple and explicit. This scheme extends naturally into an optimal CR scheme for partition matroids.

We consider the online minimum cost matching problem on the line, in which there are n servers and, at each of n time steps, a request arrives and must be irrevocably matched to a server that has not yet been matched to, with the goal of minimizing the sum of the distances between the matched pairs. Despite achieving a worst-case competitive ratio that is exponential in n, the simple greedy algorithm, which matches each request to its nearest available free server, performs very well in practice. A major question is thus to explain greedy's strong empirical performance. In this paper, we aim to understand the performance of greedy over instances that are at least partially random. When both the requests and the servers are drawn uniformly and independently from [0,1], we show that greedy is constant competitive, which improves over the previously best-known O(?n) bound. We extend this constant competitive ratio to a setting with a linear excess of servers, which improves over the previously best-known O(log^3n) bound. We moreover show that in the semi-random model where the requests are still drawn uniformly and independently but where the servers are chosen adversarially, greedy achieves an O(log n) competitive ratio. When the requests arrive in a random order but are chosen adversarially, it was previously known that greedy is O(n)-competitive. Even though this one-sided randomness allows a large improvement in greedy's competitive ratio compared to the model where requests are adversarial and arrive in a random order, we show that it is not sufficient to obtain a constant competitive ratio by giving a tight ?(logn) lower bound. These results invite further investigation about how much randomness is necessary and sufficient to obtain strong theoretical guarantees for the greedy algorithm for online minimum cost matching, on the line and beyond.