September 19 - 23, 2022
Institut d'Etudes Scientifiques de Cargèse, Corsica (France)
The yearly Cargese workshop aims to bring together researchers in combinatorial optimization around a chosen topic of current interest. It is intended to be a forum for the exchange of recent developments and powerful tools, with an emphasis on theory. Other goals include the promotion of interactions between participants and discussions of open problems.
Mathematicians are known to be the only ones that can lay down in a sofa, close their eyes and pretend to work.
We propose to swap the sofa for a hammock... Do you want to join?
This edition's workshop will focus on "Polyhedral Combinatorics".
The workshop will be hosted by L'Institut d'Études Scientifiques de Cargèse (IESC). This year's organizers are:
The organizers receive advise from the steering commitee, consisting of Fritz Eisenbrand, Michel Goemans, Monique Laurent, and R. Ravi.
There will be morning and afternoon sessions. Morning sessions will be dedicated to longer survey-type talks or open problems. The afternoon sessions will be dedicated to discussions as well as shorter talks on related topics.
In their spare time, we encourage researchers to enjoy the beautiful landscape and opportunities of the island, besides solving a few open problems.
A detailed schedule is available here.
Given a multigraph G = (V,E), the edge-coloring problem (ECP) is to color the edges of G with the minimum number of colors so that no two adjacent edges have the same color. This problem can be naturally formulated as an integer program, and its linear programming relaxation is referred to as the fractional edge-coloring problem (FECP). The optimal value of ECP (resp. FECP) is called the chromatic index (resp. fractional chromatic index) of G, denoted by χ′(G) (resp. χ*(G)). Let Δ(G) be the maximum degree of G and let ω*(G) be the density of G, defined by ω*(G) = max{2|E(U)| / (|U|-1) : U ⊆ V, |U|≥ 3 and odd} where E(U) is the set of all edges of G with both ends in U. Clearly, max{Δ(G), ⌈ω*(G)⌉} is a lower bound for χ′(G). As shown by Seymour, χ*(G) = max{Δ(G), ω*(G)}. In the early 1970s Goldberg and Seymour independently conjectured that χ′(G) ≤ max{Δ(G) + 1, ⌈ω*(G)⌉}. Over the past five decades this conjecture, a cornerstone in modern edge-coloring, has been a subject of extensive research, and has stimulated an important body of work. This outstanding conjecture was recently confirmed by Guangming Jing, Wenan Zang and the speaker. Our result implies that, first, there are only two possible values for χ′(G), so an analogue to Vizing’s theorem on edge-colorings of simple graphs holds for multigraphs; second, although it is NP-hard in general to determine χ′(G), we can approximate it within one of its true value, and find it exactly in polynomial time when ω(G) > Δ(G); third, every multigraph G satisfies χ′(G) - χ*(G) ≤ 1, and thus FECP has a fascinating integer rounding property.
This lecture consists of three talk. In the first talk, I will give a brief survey of the history and previous progress on this conjecture. In the second talk, I will focus on the proof methods and techniques of this conjecture. In the third talk, I will provide several consequences of the conjecture and its generalization form in f-coloring of weighted graphs. (slides 1, slides 2, slides 3)
In the first lecture (Overview), we introduce the notion of clutters, blocking theory, Lehman's characterization of ideal clutters, the packing property, the replication conjecture, the tau=2 conjecture and several recent results in the area. (slides)
In the second lecture (Woodall's conjecture), we introduce the notions of a dicut and a dijoin in a directed graph, the Lucchesi-Younger theorem as well as recent developments on Woodall's conjecture. In particular we present recent results obtained jointly with Ahmad Abdi and Michael Zlatin. (slides)
In the third lecture (Seymour's conjecture), we present an intriguing conjecture of Seymour on packing members of an ideal clutter. We show that the conjecture holds in two special cases in joint work with Ahmad Abdi, Bertrand Guenin and Levent Tuncel in one instance, and with Ahmad Abdi and Zuzana Palion in the other instance. (slides)
In these lectures, based on joint work with Matthew Kwan and Yufei Zhao, we discuss several results concerning the extension complexity of various families of low-dimensional polytopes. First, for a fixed dimension d, we consider random d-dimensional polytopes (obtained as the convex hull of random points in a ball or on a sphere) and show that their extension complexity is typically on the order of the square root of its number of vertices. Second, we prove that any cyclic n-vertex polygon (whose vertices lie on a circle) has extension complexity at most 24 sqrt(n). This bound is tight up to the constant factor 24. The lectures will introduce the relevant background, and explain (most of) the proofs of these results.
Bounding the combinatorial diameter of a polytope is a well-known and long-standing open problem. The great theoretical and practical interest in this question originates from the desire to efficiently solve linear programming. In this regard, since the ultimate goal is to optimize over polytopes, it is well worth looking at extended formulations as well. In this talk we will discuss polytope extensions having surprisingly small combinatorial diameter. Joint work with Volker Kaibel.
One appealing way of integrating fairness aspects into classical clustering problems is by introducing multiple covering constraints. While prior techniques assume covering constraints on the clients, they do not address additional constraints on the facilities, which has been extensively studied in non-colorful settings. In this talk, we present a framework to deal with various constraints on the facilities in the colorful setting. To exemplify our framework, we show how it leads, to a O(2^\gamma)-approximation for Colorful Matroid Supplier with respect to a linear matroid. Joint work with Georg Anegg and Rico Zenklusen (published at ESA 22).
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 be uncrossable and allow for a certain oracle access. Our setting generalizes many problems that were studied separately in the past. Among our corollaries are the first constant-factor approximation algorithm for vertex-disjoint paths in fully planar instances and approximate min-max theorems of the Erdős-Pósa type. This is joint work with Niklas Schlomberg and Hanjo Thiele (arXiv:2207.00450).
We consider two-sided matching markets in which indivisible distinguishable goods are sold to a set of buyers with individual valuation functions over sets of bundles. Item prices which admit a distribution of items to buyers such that every buyer receives a preferred bundle are called Walrasian equilibrium prices. In 1982, Kelso and Crawford proposed a gross substitute condition for the existence of Walrasian equilibrium prices. Gul and Stacchetti showed in 1999 that they can be computed by an ascending auction which starts with all-zero prices and iteratively increases the prices on overdemanded sets until the prices are Walrasian. Murota et al. gave combinatorial algorithms for computing Walrasian equilibria by using the theory of discrete convexity. In this talk, we show that minimal Walrasian prices can be computed via the matroid partitioning algorithm. Structural insights obtained from this algorithm allow us to derive sensitivity results regarding possible changes in supply and demand. Joint work with Britta Peis, Niklas Rieken, and Laura Vargas Koch.
Given a finite set X of integer points, a relaxation of X is a polyhedron whose integer points are exactly those of X. The relaxation complexity of X is the smallest number of facets of a relaxation of X. In this article, we focus on X being the vertex set of the standard simplex, which consists of the null vector and the standard unit vectors. We show that, for dimension d at least 5, the relaxation complexity of X is at most d. This answer an open question of Kaibel and Weltge, implying that irrational relaxations can be smaller than rational ones (indeed, the best rational relaxation of X is the standard simplex itself, with d+1 facets). Moreover, we improve our bound showing that the relaxation complexity of X is asymptotically sublinear.
In the Unsplittable Flow on a Path problem (UFP) we are given a path with edge capacities, and a set of tasks where each task is characterized by a subpath, a demand, and a weight. The goal is to select a subset of tasks of maximum total weight such that the total demand of the selected tasks using each edge $e$ is at most the capacity of $e$. The problem admits a QPTAS [Bansal, Chakrabarti, Epstein, Schieber, STOC'06; Batra, Garg, Kumar, M{\"o}mke, Wiese, SODA'15]. After a long sequence of improvements [Bansal, Friggstad, Khandekar, Salavatipour, SODA'09; Bonsma, Schulz, Wiese, FOCS'11; Anagnostopoulos, Grandoni, Leonardi, Wiese, SODA'14; Grandoni, M{\"o}mke, Wiese, Zhou, STOC'18], the best known polynomial time approximation algorithm for UFP has an approximation ratio of $1+\frac{1}{e+1}+\eps < 1.269$ [Grandoni, M{\"o}mke, Wiese, SODA'22]. It has been an open question whether this problem admits a PTAS. In this paper, we solve this open question and present a polynomial time $(1+\eps)$-approximation algorithm for UFP. Joint work with Fabrizio Grandoni and Tobais Mömke.
"Online optimization refers to solving problems where an initially unknown input is revealed incrementally, and irrevocable decisions must be made not knowing future requests. The assumption of not having any prior knowledge about future requests seems overly pessimistic. Given the success of machine-learning methods and data-driven applications, one may expect to have access to predictions about future requests. However, simply trusting them might lead to very poor solutions as these predictions come with no quality guarantee. In this talk we present recent developments in the young line of research that integrates such error-prone predictions into algorithm design to break through worst case barriers. We discuss algorithmic challenges with a focus on online routing and network design and present algorithms with performance guarantees depending on a novel error metric. Joint work with Giulia Bernardini, Alexander Lindermayr, Alberto Marchetti-Spaccamela, Leen Stougie, and Michelle Sweering.
For 75 years, the simplex method has remained one of the most popular methods for solving linear programs, yet much still remains mysterious about its performance. Geometrically, the simplex method optimizes a linear function by tracing a path on the oriented graph of a polyhedron, and the simplex method may only run quickly if this graph has small diameter. It is a fundamental open question to understand whether polyhedra are guaranteed to have polynomially bounded diameters. However, even in cases in which we know bounds on diameters, actually following such short paths with the simplex method has continued to be an additional challenge. I will talk about my recent joint work with Jesús De Loera, Sean Kafer, and Laura Sanità on finding pivot rules for the simplex method guaranteed to match the theoretical best possible bound on diameters for 0/1-polytopes as well as my work on nearly matching the best known bounds for lattice polytopes.
For a subset of terminals T of the nodes of a graph G a cut in G is called a T-Steiner cut if it subdivides T into two non-empty sets. The Steiner cut dominant of G is the Minkowski sum of the convex hull of the incidence vectors of T-Steiner cuts in G and the nonnegative orthant. It is the polyhedron that is naturally associated with the problem of finding a minimum T-Steiner cut in G w.r.t. nonnegative edge weights. While it is well understood for two terminals (s-t-cuts), for larger sets T no inequality descriptions have been known so far despite quite some efforts that have been spent into investigating this problem for T being the complete node set of G (global cuts). In this talk we derive such descriptions for all graphs and up to five terminals. Moreover, we prove that for each number k there is a finite list of inequalities from which one can derive by means of iterated applications of two simple operations inequality descriptions of the Steiner cut dominant for every graph and up to k terminals. We furthermore introduce the concept of the Steiner rank of a facet of a global cut dominant and classify the facets of Steiner rank at most five. Via blocking duality those results yield corresponding results for the vertices of the subtour elimination polytope that is most relevant in the context of the traveling salesman problem.
"When solving integer linear programs (ILPs), it is common to face problems subject to symmetries. Usual IP techniques struggle with highly symmetric instances if they are not addressed appropriately. Breaking symmetries is arguably the simplest way of speeding up such methods for symmetric ILPs. However, there might be several non-equivalent ways of breaking symmetries, so it is relevant to understand the geometric differences between constructions. In this talk I will show how the theory of vector orderings relates to symmetry breaking and how this connection conceptually simplifies the construction of symmetry-breaking inequalities found in the literature. We will be able to characterize all constructions of minimal symmetry breaking sets (i.e. fundamental domains) that arise from vector orderings by showing that, in essence, all such sets arise from choosing lexicographically minimal representative of symmetric points (after a corresponding change of basis). We will finish with several conjectures and open questions.
The (combinatorial) diameter diam(P) of a polytope P is the maximum shortest path distance between any pair of vertices. We provide upper and lower bounds on the combinatorial diameter of a random "spherical" polytope, which is tight to within one factor of dimension when the number of inequalities is large compared to the dimension. More precisely, for an n-dimensional polytope P defined by the intersection of m i.i.d. half-spaces whose normals are chosen uniformly from the sphere, we show diam(P) is between Omega(n m^{1/(n-1)}) and O(n^2 m^{1/(n-1)} + n^5 4^n) with high probability when m > 2^Omega(n). In this talk, I will prove a simpler lower bound and sketch how to derive the upper bound from this lower bound.
Whereas interior point methods provide polynomial-time linear programming algorithms, the running time bounds depend on bit-complexity or condition measures that can be unbounded in the problem dimension. This is in contrast with the simplex method that always admits an exponential bound. We introduce a new polynomial-time path-following interior point method where the number of iterations also admits a combinatorial upper bound O(2^n n^{1.5} log n) for an n-variable linear program in standard form. This complements previous work by Allamigeon, Benchimol, Gaubert, and Joswig (SIAGA 2018) that exhibited a family of instances where any path-following method must take exponentially many iterations. The number of iterations of our algorithm is at most O(n^{1.5} log n) times the number of segments of any piecewise linear curve in the wide neighborhood of the central path. In particular, it matches the number of iterations of any path following interior point method up to this polynomial factor. The overall exponential upper bound derives from studying the `max central path', a piecewise-linear curve with the number of pieces bounded by the total length of 2n shadow vertex simplex paths. Our algorithm falls into the family of layered least squares interior point methods introduced by Vavasis and Ye (Math. Prog. 1996). In contrast to previous layered least squares methods that partition the kernel of the constraint matrix into coordinate subspaces, our method creates layers based on a general subspace providing more flexibility. Our result also implies the same bound on the number of iterations of the trust region interior point method by Lan, Monteiro, and Tsuchiya (SIOPT 2009). This is joint work with Xavier Allamigeon, Daniel Dadush, Georg Loho, and László Végh.
In line with recent research studying neural networks with rectified linear units (ReLUs) from a polyhedral point of view, we pose the following question about this fundamental machine learning model: Which (continuous and piecewise linear) functions can exactly be represented by a ReLU neural network of polynomial size? In order to study this question, we propose to view neural networks as a model of (real-valued!) computation and investigate the complexity of different problems in this model. Specifically, we show that there exist polynomial-size neural networks (i) to compute the value of a minimum spanning tree from given edge weights in a graph, and (ii) to compute a maximum s-t-flow from given arc capacities in a flow network. These results imply in particular that the respective problems can be solved with strongly polynomial time algorithms that solely use affine transformations and maxima computations, but no conditional branchings. This is joint work with Leon Sering (ETHZ).
Let M be a matroid and let M* denote its dual. A conjecture of White states that for any two vertices of the common basis polytope of M and M*, there exists a path between them containing only short edges. Here an edge between two vertices B and B' is called short if B'=B-e+f, that is, B' can be obtained from B by a single exchange. The conjecture was shown to hold for graphic, lattice path, strongly base orderable, and frame matroids, but it is open in general. Hamidoune formulated an even more optimistic conjecture stating that not only the above-mentioned path exists, but its length can be bounded by the rank of the matroid. This was proved for transversal matroids, but remained open even e.g. for sparse paving matroids. We verify the conjecture for split matroids, a class that was motivated by the study of matroid polytopes from a tropical geometry point of view.
We show that a constant factor approximation of the shortest and closest lattice vector problem in any norm can be computed in time $2^{0.802n}$. This contrasts the corresponding $2^n$ time, (gap)-SETH based lower bounds for these problems that even apply for small constant approximation. For both problems, SVP and CVP, we reduce to the case of the Euclidean norm. A key technical ingredient in that reduction is a twist of Milman's construction of an $M$-ellipsoid which approximates any symmetric convex body $K$ with an ellipsoid $E$ so that $2^{\varepsilon n}$ translates of a constant scaling of $E$ can cover $K$ and vice versa. This is joint work with Moritz Venzin.
Several participants posed interesting problems during the open problem session. A transcript of all open problems that have been raised can be found here.
On Thursday afternoon, we will have a hike at the Calanques de Piana. There is a bus leaving at 1:30 pm from the institute to the bar Les Roches Bleues. From there, we will follow a round trip of about 3.4 km (~ 1:30 h).
A list of all previous editions can be found here.
Logo designed by Giuseppe Musolino. Website hosted at GitHub Pages. Layout based on skeleton using AmatiSC font.