We consider the matroid prophet inequality problem. This problem has been extensively studied in the case of adaptive mechanisms. In particular, there is a tight 2-competitive mechanism for all matroids (Kleinberg and Weinberg, 2012). However, it is not known what classes of matroids admit non-adaptive mechanisms with constant guarantee. Recently, in Chawla et al. (2024) it was shown that there are constant-competitive non-adaptive mechanisms for graphic matroids. In this work, we show that various known classes of matroids admit constant-competitive non-adaptive mechanisms.

The combinatorial diameter of a polytope $P$ is the maximum value of a shortest path between two vertices of $P$, where the path uses the edges of $P$ only. In contrast to the combinatorial diameter, the circuit diameter of $P$ is defined as the maximum value of a shortest path between two vertices of $P$, where the path uses potential edge directions of $P$, i.e., all edge directions that can arise by translating some of the facets of $P$. In this paper, we study the circuit diameter of polytopes corresponding to classical combinatorial optimization problems, such as the matching polytope, the Traveling Salesman polytope, and the fractional stable set polytope.

For an integer $n\geq 3$, the clutter $\Delta_n:=\big\{\{1,2\},\{1,3\},\ldots,\{1,n\},\{2,3,\ldots,n\}\big\}$ is called a delta of dimension $n$, whose members are the lines of a degenerate projective plane. In his seminal paper on nonideal clutters, Lehman revealed the role of the deltas as a distinct class of minimally nonideal clutters [ The width length inequality and degenerate projective planes, DIMACS Ser. Discrete Math. Theoret. Comput. Sci. 1, AMS, Providence, RI, 1990, pp. 101--105]. A clutter is delta free if it has no delta minor. Binary clutters, ideal clutters, and clutters with the packing property are examples of delta free clutters. In this paper, we introduce and study basic geometric notions defined on clutters, including entanglement between clutters, a notion that is intimately linked with set covering polyhedra having a convex union. We will then investigate the surprising geometric attributes of delta minors and delta free clutters.

In the prize-collecting Steiner forest (PCSF) problem, we are given an undirected graph G=(V,E), nonnegative edge costs {c_e} for e in E, terminal pairs {(s_i,t_i)} for i=1,...,k, and penalties {pi_i} for i=1,...,k for each terminal pair; the goal is to find a forest F to minimize c(F) + sum{ pi_i: (s_i,t_i) is not connected in F }. The Steiner forest problem can be viewed as the special case where pi_i are infinite for all i. It was widely believed that the integrality gap of the natural (and well-studied) linear-programming (LP) relaxation for PCSF (PCSF-LP) is at most 2. We dispel this belief by showing that the integrality gap of this LP is at least 9/4 even if the input instance is planar. We also show that using this LP, one cannot devise a Lagrangian-multiplier-preserving (LMP) algorithm with approximation guarantee better than 4. Our results thus show a separation between the integrality gaps of the LP-relaxations for prize-collecting and non-prize-collecting (i.e., standard) Steiner forest, as well as the approximation ratios achievable relative to the optimal LP solution by LMP- and non-LMP-approximation algorithms for PCSF. For the special case of prize-collecting Steiner tree (PCST), we prove that the natural LP relaxation admits basic feasible solutions with all coordinates of value at most 1/3 and all edge variables positive. Thus, we rule out the possibility of approximating PCST with guarantee better than 3 using a direct iterative rounding method.

In a standard $f$-connectivity network design problem, we are given an undirected graph $G=(V,E)$, a cut-requirement function $f:2^V \rightarrow {\mathbb{N}}$, and non-negative costs $c(e)$ for all $e \in E$. We are then asked to find a minimum-cost vector $x \in {\mathbb{N}}^E$ such that $x(δ(S)) \geq f(S)$ for all $S \subseteq V$. We focus on the class of such problems where $f$ is a proper function. This encodes many well-studied NP-hard problems such as the generalized survivable network design problem. In this paper we present the first strongly polynomial time FPTAS for solving the LP relaxation of the standard IP formulation of the $f$-connectivity problem with general proper functions $f$. Implementing Jain's algorithm, this yields a strongly polynomial time $(2+ε)$-approximation for the generalized survivable network design problem (where we consider rounding up of rationals an arithmetic operation).

The cut dominant of a graph is the unbounded polyhedron whose points are all those that dominate some convex combination of proper cuts. Minimizing a nonnegative linear function over the cut dominant is equivalent to finding a minimum weight cut in the graph. We give a forbidden-minor characterization of the graphs whose cut dominant can be defined by inequalities with integer coefficients and right-hand side at most 2. Our result is related to the forbidden-minor characterization of TSP-perfect graphs by Fonlupt and Naddef [Math. Program, 53 (1992), pp. 147--172]. We show how to derive each of the results from the other. Furthermore, we establish general properties of forbidden minors for right-hand sides larger than 2.

In 1991, Yannakakis [J. Comput. System Sci., 43 (1991), pp. 441--466] proved that no symmetric extended formulation for the matching polytope of the complete graph $K_n$ with $n$ nodes has a number of variables and constraints that is bounded subexponentially in $n$. Here, symmetric means that the formulation remains invariant under all permutations of the nodes of $K_n$. It was also conjectured by Yannakakis that “asymmetry does not help much,” but no corresponding result for general extended formulations has been found so far. In this paper we show that for the polytopes associated with the matchings in $K_n$ with $\lfloor\log n\rfloor$ edges there are nonsymmetric extended formulations of polynomial size, while nevertheless no symmetric extended formulations of polynomial size exist. We furthermore prove similar statements for the polytopes associated with cycles of length $\lfloor\log n\rfloor$. Thus, with respect to the question for smallest possible extended formulations, in general symmetry requirements may matter a lot. Compared to the extended abstract [Integer Pgrogramming and Combinatiorial Optimization, Lecture Notes in Comput. Sci. 6080, Springer, New York, 2010, pp. 135--148], this paper not only contains proofs that had been omitted there but also presents slightly generalized and sharpened lower bounds.