We show that if the ground set of a matroid can be partitioned into \(k \ge 2\) bases, then for any given subset \(S\) of the ground set, there is a partition into k bases such that the sizes of the intersections of the bases with \(S\) may differ by at most one. This settles the matroid equitability conjecture by Fekete and Szabo (Electron. J. Comb. 2011) in the affirmative. We also investigate equitable splittings of two disjoint sets \(S_1\) and \(S_2\), and show that there is a partition into \(k\) bases such that the sizes of the intersections with \(S_1\) may differ by at most one and the sizes of the intersections with \(S_2\) may differ by at most two; this is the best one can hope for arbitrary matroids.

We provide faster strongly polynomial time algorithms solving maximum flow in structured \(n\)-node \(m\)-arc networks. Our results imply an \(n^{\omega+o(1)}\)-time strongly polynomial time algorithms for computing a maximum bipartite \(b\)-matching where \(\omega\) is the matrix multiplication constant. Additionally, they imply an \(m^{1+o(1)}W\)-time algorithm for solving the problem on graphs with a given tree decomposition of width \(W\).

For any ɛ > 0, we give a simple, deterministic (4+ɛ)-approximation algorithm for the Nash social welfare (NSW) problem under submodular valuations. We also consider the asymmetric variant of the problem, where the objective is to maximize the weighted geometric mean of agents’ valuations, and give an e(ω + 2 + ɛ)-approximation if the ratio between the largest weight and the average weight is at most ω. We also show that the 1/2-EFX envy-freeness property can be attained simultaneously with a constant-factor approximation. More precisely, we can find an allocation in polynomial time that is both 1/2-EFX and an (8+ɛ)-approximation to the symmetric NSW problem under submodular valuations.

We explore the relationship between two popular concepts in the allocation of divisible items: competitive equilibrium (CE) and allocations that maximize Nash welfare, i.e., allocations where the weighted geometric mean of the utilities is maximal. When agents have homogeneous concave utility functions, these two concepts coincide: the classical Eisenberg- Gale convex program that maximizes Nash welfare over feasible allocations yields a competitive equilibrium. However, these two concepts diverge for non-homogeneous utilities. From a computational perspective, maximizing Nash welfare amounts to solving a convex program for any concave utility functions, whereas computing CE becomes PPAD-hard already for separable piecewise linear concave (SPLC) utilities.

Abstract. We develop a new “subspace layered least squares" interior point method (IPM) for solving linear programs. Applied to an [Formula: see text]-variable linear program in standard form, the iteration complexity of our IPM is up to an [Formula: see text] factor upper bounded by the straight-line complexity (SLC) of the linear program. This term refers to the minimum number of segments of any piecewise linear curve that traverses the wide neighborhood of the central path, a lower bound on the iteration complexity of any IPM that follows a piecewise linear trajectory along a path induced by a self-concordant barrier. In particular, our algorithm matches the number of iterations of any such IPM up to the same factor [Formula: see text]. As our second contribution, we show that the SLC of any linear program is upper bounded by [Formula: see text], which implies that our IPM’s iteration complexity is at most exponential. This is in contrast to existing iteration complexity bounds that depend on either bit complexity or condition measures; these can be unbounded in the problem dimension. We achieve our upper bound by showing that the central path is well-approximated by a combinatorial proxy we call the max central path, which consists of [Formula: see text] shadow vertex simplex paths. Our upper bound complements the lower bounds of Allamigeon et al. [ SIAM J. Appl. Algebra Geom., 2 (2018), pp. 140–178] and Allamigeon, Gaubert, and Vandame [ No self-concordant barrier interior point method is strongly polynomial, 2022], who constructed linear programs with exponential SLC. Finally, we show that each iteration of our IPM can be implemented in strongly polynomial time. Along the way, we develop a deterministic algorithm that approximates the singular value decomposition of a matrix in strongly polynomial time to high accuracy, which may be of independent interest.

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 Végh ‍(MOR ’17) and Megiddo ‍(SICOMP ’83), 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) by 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 and extreme rays. Our approach is black-box and can be applied to any log-barrier path-following method.

Optimal auction design is a fundamental problem in algorithmic game theory. This problem is notoriously difficult already in very simple settings. Recent work in differentiable economics showed that neural networks can efficiently learn known optimal auction mechanisms and discover interesting new ones. In an attempt to theoretically justify their empirical success, we focus on one of the first such networks, RochetNet, and a generalized version for affine maximizer auctions. We prove that they satisfy mode connectivity, i.e., locally optimal solutions are connected by a simple, piecewise linear path such that every solution on the path is almost as good as one of the two local optima. Mode connectivity has been recently investigated as an intriguing empirical and theoretically justifiable property of neural networks used for prediction problems. Our results give the first such analysis in the context of differentiable economics, where neural networks are used directly for solving non-convex optimization problems.

For any >0, we give a simple, deterministic (4+)-approximation algorithm for the Nash social welfare (NSW) problem under submodular valuations. The previous best approximation factor was 380 via a randomized algorithm. We also consider the asymmetric variant of the problem, where the objective is to maximize the weighted geometric mean of agents’ valuations, and give an (ω + 2 + ) -approximation if the ratio between the largest weight and the average weight is at most ω.

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^{15}\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^{15}\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. From the existence of a line segment in the wide neighborhood we derive strong implications on the structure of the corresponding segment of the central path. Our algorithm is able to detect this structure from the local geometry at the current iterate, and constructs a step direction that descends along this segment. The bound $O(n^{15}\log n)$ that applies for arbitrarily long line segments is derived from a combinatorial progress measure. 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).

We consider linear programming in the oracle model: mincT x s.t. x ∊ P, where the polyhedron P = {x ∊ ℝn: Ax ≤ b} is given by a separation oracle that returns violated inequalities from the system Ax ≤ b. We present an algorithm that finds exact primal and dual solutions using O(n2 log(n/δ)) oracle calls and O(n4 log(n/δ) + n6 log log(1/δ)) arithmetic operations, where δ is a geometric condition number associated with the system (A, b). These bounds do not depend on the cost vector c. The algorithm works in a black box manner, requiring a subroutine for approximate primal and dual solutions; the above running times are achieved when using the cutting plane method of Jiang, Lee, Song, and Wong (STOC 2020) for this subroutine. Whereas approximate solvers may return primal solutions only, we develop a general framework for extracting dual certificates based on the work of Burrell and Todd (Math. Oper. Res. 1985). Our algorithm works in the real model of computation, and extends results by Grötschel, Lovász, and Schrijver (Prog. Comb. Opt. 1984), and by Frank and Tardos (Combinatorica 1987) on solving LPs in the bit-complexity model. We show that under a natural assumption, simultaneous Diophantine approximation in these results can be avoided.

We study the equilibrium computation problem in the Fisher market model with constrained piecewise linear concave (PLC) utilities. This general class captures many well-studied special cases, including markets with PLC utilities, markets with satiation, and matching markets. For the special case of PLC utilities, although the problem is PPAD-hard, Devanur and Kannan (FOCS 2008) gave a polynomial-time algorithm when the number of goods is constant. Our main result is a fixed parameter approximation scheme for computing an approximate equilibrium, where the parameters are the number of agents and the approximation accuracy. This provides an answer to an open question by Devanur and Kannan for PLC utilities, and gives a simpler and faster algorithm for matching markets as the one by Alaei, Jalaly and Tardos (EC 2017). The main technical idea is to work with the stronger concept of thrifty equilibria, and approximating the input utility functions by ‘robust’ utilities that have favorable marginal properties. With some restrictions, the results also extend to the Arrow–Debreu exchange market model.

We characterize a rich class of valuated matroids, called R-minor valuated matroids that includes the indicator functions of matroids, and is closed under operations such as taking minors, duality, and induction by network. We exhibit a family of valuated matroids that are not R-minor based on sparse paving matroids. Valuated matroids are inherently related to gross substitute valuations in mathematical economics. By the same token we refute the Matroid Based Valuation Conjecture by Ostrovsky and Paes Leme (Theoretical Economics 2015) asserting that every gross substitute valuation arises from weighted matroid rank functions by repeated applications of merge and endowment operations. Our result also has implications in the context of Lorentzian polynomials: it reveals the limitations of known construction operations.

We present an O(nm) algorithm for all-pairs shortest paths computations in a directed graph with n nodes, m arcs, and nonnegative integer arc costs. This matches the complexity bound attained by Thorup [26] for the all-pairs problems in undirected graphs. Our main insight is that shortest paths problems with approximately balanced directed cost functions can be solved similarly to the undirected case. Our algorithm starts with an preprocessing step that finds a 3-min-balanced reduced cost function. Using these reduced costs, every shortest path query can be solved in O(m) time using an adaptation of Thorup's component hierarchy method. The balancing result is of independent interest, and gives the best currently known approximate balancing algorithm for the problem.

We consider the Arrow--Debreu exchange market model under the assumption that the agents' demands satisfy the weak gross substitutes (WGS) property. We present a simple auction algorithm that obtains an approximate market equilibrium for WGS demands assuming the availability of a price update oracle. We exhibit specific implementations of such an oracle for WGS demands with bounded price elasticities and for Gale demand systems. As an application of our result, we obtain an efficient algorithm to find an approximate spending-restricted market equilibrium for WGS demands, a model that has been recently introduced as a continuous relaxation of the Nash social welfare (NSW) problem. This leads to a polynomial-time constant factor approximation algorithm for the NSW problem with capped additive separable piecewise linear utility functions; only a pseudopolynomial approximation algorithm was known for this setting previously.

The Nash social welfare problem asks for an allocation of indivisible items to agents in order to maximize the geometric mean of agents' valuations. We give an overview of the constant-factor approximation algorithm for the problem when agents have Rado valuations [Garg et al. 2021]. Rado valuations are a common generalization of the assignment (OXS) valuations and weighted matroid rank functions. Our approach also gives the first constant-factor approximation algorithm for the asymmetric Nash social welfare problem under the same valuations, provided that the maximum ratio between the weights is bounded by a constant.

In breakthrough work, Tardos (Oper. Res. '86) gave a proximity based framework for solving linear programming (LP) in time depending only on the constraint matrix in the bit complexity model. In Tardos's framework, one reduces solving the LP min(c, x), Ax=b, x ≥ 0, A Zm×n, to solving O(nm) LPs in A having small integer coefficient objectives and right-hand sides using any exact LP algorithm. This gives rise to an LP algorithm in time poly (n, m log ΔA), where ΔAis the largest subdeterminant of A. A significant extension to the real model of computation was given by Vavasis and Ye (Math. Prog. '96), giving a specialized interior point method that runs in time poly (n, m,log χ̑A), depending on Stewart's χ̑A, a well-studied condition number. In this work, we extend Tardos's original framework to obtain such a running time dependence. In particular, we replace the exact LP solves with approximate ones, enabling us to directly leverage the tremendous recent algorithmic progress for approximate linear programming. More precisely, we show that the fundamental “accuracy” needed to exactly solve any LP in A is inverse polynomial in n and log χ̑A. Plugging in the recent algorithm of van den Brand (SODA '20), our method computes an optimal primal and dual solution using O(mnω+1+0(1)log(χ̑A+n)) arithmetic operations, outperforming the specialized interior point method of Vavasis and Ye and its recent improvement by Dadush et al (STOC '20). By applying the preprocessing algorithm of the latter paper, the dependence can also be reduced from χ̑Ato χ̑A*, the minimum value of χ̑ADattainable via column rescalings. Our framework is applicable to achieve the poly (n, m,log χ̑A*) bound using essentially any weakly polynomial LP algorithm, such as the ellipsoid method. At a technical level, our framework combines together approximate LP solutions to compute exact ones, making use of constructive proximity theorems-which bound the distance between solutions of “nearby” LPs-to keep the required accuracy low.

We establish a new notion of tropical convexity for signed tropical numbers. We provide several equivalent descriptions involving balance relations and intersections of open halfspaces as well as the image of a union of polytopes over Puiseux series and hyperoperations. Along the way, we deduce a new Farkas' lemma and Fourier-Motzkin elimination without the non-negativity restriction on the variables. This leads to a Minkowski-Weyl theorem for polytopes over the signed tropical numbers.

Following the breakthrough work of Tardos (Oper. Res. ’86) in the bit-complexity model, Vavasis and Ye (Math. Prog. ’96) gave the first exact algorithm for linear programming in the real model of computation with running time depending only on the constraint matrix. For solving a linear program (LP) max c x, Ax = b, x ≥ 0, A ∈ m × n , Vavasis and Ye developed a primal-dual interior point method using a ‘layered least squares’ (LLS) step, and showed that O(n 3.5 log(χ A +n)) iterations suffice to solve (LP) exactly, where χ A is a condition measure controlling the size of solutions to linear systems related to A.

We present a new strongly polynomial algorithm for generalized flow maximization that is significantly simpler and faster than the previous strongly polynomial algorithm [34]. For the uncapacitated problem formulation, the complexity bound O ( mn ( m + n log n )log ( n 2 / m )) improves on the previous estimate by almost a factor O ( n 2 ). Even for small numerical parameter values, our running time bound is comparable to the best weakly polynomial algorithms. The key new technical idea is relaxing the primal feasibility conditions. This allows us to work almost exclusively with integral flows, in contrast to all previous algorithms for the problem.

We give a constant-factor approximation algorithm for the asymmetric traveling salesman problem (ATSP). Our approximation guarantee is analyzed with respect to the standard LP relaxation, and thus our result confirms the conjectured constant integrality gap of that relaxation. The main idea of our approach is a reduction to Subtour Partition Cover, an easier problem obtained by significantly relaxing the general connectivity requirements into local connectivity conditions. We first show that any algorithm for Subtour Partition Cover can be turned into an algorithm for ATSP while only losing a small constant factor in the performance guarantee. Next, we present a reduction from general ATSP instances to structured instances, on which we then solve Subtour Partition Cover, yielding our constant-factor approximation algorithm for ATSP.

We present a strongly polynomial algorithm for computing an equilibrium in Arrow-Debreu exchange markets with linear utilities. Our algorithm is based on a variant of the weakly-polynomial Duan-Mehlhorn (DM) algorithm. We use the DM algorithm as a subroutine to identify revealed edges, i.e., pairs of agents and goods that must correspond to best bang-per-buck transactions in every equilibrium solution. Every time a new revealed edge is found, we use another subroutine that decides if there is an optimal solution using the current set of revealed edges, or if none exists, finds the solution that approximately minimizes the violation of the demand and supply constraints. This task can be reduced to solving a linear program (LP). Even though we are unable to solve this LP in strongly polynomial time, we show that it can be approximated by a simpler LP with two variables per inequality that is solvable in strongly polynomial time.

We present a new class of polynomial-time algorithms for submodular function minimization (SFM), as well as a unified framework to obtain strongly polynomial SFM algorithms. Our new algorithms are based on simple iterative methods for the minimum-norm problem, such as the conditional gradient and the Fujishige-Wolfe algorithms. We exhibit two techniques to turn simple iterative methods into polynomial-time algorithms. Firstly, we use the geometric rescaling technique, which has recently gained attention in linear programming. We adapt this technique to SFM and obtain a weakly polynomial bound O((n4 · EO + n5) log(nL)). Secondly, we exhibit a general combinatorial black-box approach to turn any strongly polynomial εL-approximate SFM oracle into an strongly polynomial exact SFM algorithm. This framework can be applied to a wide range of combinatorial and continuous algorithms, including pseudopolynomial ones. In particular, we can obtain strongly polynomial algorithms by a repeated application of the conditional gradient or of the Fujishige-Wolfe algorithm. Combined with the geometric rescaling technique, the black-box approach provides a O((n5 · EO + n6) log2 n) algorithm. Finally, we show that one of the techniques we develop in the paper, “sliding”, can also be combined with the cutting-plane method of Lee, Sidford, and Wong [27], yielding a simplified variant of their O(n3 log2 n · EO + n4 logO(1) n) algorithm.

We give a constant-factor approximation algorithm for the asymmetric traveling salesman problem. Our approximation guarantee is analyzed with respect to the standard LP relaxation, and thus our result confirms the conjectured constant integrality gap of that relaxation.

We investigate problems addressing combined connectivity augmentation and orientations settings. We give a polynomial-time 6-approximation algorithm for finding a minimum cost subgraph of an undirected graph $G$ that admits an orientation covering a nonnegative crossing $G$-supermodular demand function, as defined by Frank [ J. Comb. Theory Ser. B, 28 (1980), pp. 251--261]. An important example is $(k,\ell)$-edge-connectivity, a common generalization of global and rooted edge-connectivity. Our algorithm is based on a nonstandard application of the iterative rounding method. We observe that the standard linear program with cut constraints is not amenable and use an alternative linear program with partition and copartition constraints instead. The proof requires a new type of uncrossing technique on partitions and copartitions. We also consider the problem setting when the cost of an edge can be different for the two possible orientations. The problem becomes substantially more difficult already for the simpler requirement of $k$-edge-connectivity. Khanna, Naor, and Shepherd [ SIAM J. Discrete Math., 19 (2005), pp. 245--257] showed that the integrality gap of the natural linear program is at most $4$ when $k=1$ and conjectured that it is constant for all fixed $k$. We disprove this conjecture by showing an $\Omega(|V|)$ integrality gap even when $k=2$.

This paper investigates connections between discrete and continuous approaches for decomposable submodular function minimization. We provide improved running time estimates for the state-of-the-art continuous algorithms for the problem using combinatorial arguments. We also provide a systematic experimental comparison of the two types of methods, based on a clear distinction between level-0 and level-1 algorithms.

We present a new strongly polynomial algorithm for generalized flow maximization. The first strongly polynomial algorithm for this problem was given very recently by Végh; our new algorithm is much simpler, and much faster. The complexity bound O((m+nlogn)mnlog(n2/m)) improves on the previous estimate obtained by Végh by almost a factor O(n2). Even for small numerical parameter values, our algorithm is essentially as fast as the best weakly polynomial algorithms. The key new technical idea is relaxing primal feasibility conditions. This allows us to work almost exclusively with integral flows, in contrast to all previous algorithms.

We consider the minimum-weight feedback vertex set problem in tournaments: given a tournament with non-negative vertex weights, remove a minimum-weight set of vertices that intersects all cycles. This problem is $\mathsf{NP}$-hard to solve exactly, and Unique Games-hard to approximate by a factor better than 2. We present the first $7/3$ approximation algorithm for this problem, improving on the previously best known ratio $5/2$ given by Cai et al. [FOCS 1998, SICOMP 2001].

A well-studied nonlinear extension of the minimum-cost flow problem is to minimize the objective $\sum_{ij\in E}C_{ij}(f_{ij})$ over feasible flows $f$, where on every arc $ij$ of the network, $C_{ij}$ is a convex function. We give a strongly polynomial algorithm for the case when all $C_{ij}$'s are convex quadratic functions, settling an open problem raised, e.g., by Hochbaum [Math. Oper. Res., 19 (1994), pp. 390--409]. We also give strongly polynomial algorithms for computing market equilibria in Fisher markets with linear utilities and with spending constraint utilities that can be formulated in this framework (see Shmyrev [J. Appl. Ind. Math., 3 (2009), pp. 505--518], Birnbaum, Devanur, and Xiao [Proceedings of the 12th ACM Conference on Electronic Commerce, 2011, pp. 127--136]). For the latter class this resolves an open question raised by Vazirani [Math. Oper. Res., 35 (2010), pp. 458--478]. The running time is $O(m^4\log m)$ for quadratic costs, $O(n^4+n^2(m+n\log n)\log n)$ for Fisher's markets with linear utilities, and $O(mn^3+m^2(m+n\log n)\log m)$ for spending constraint utilities. All these algorithms are presented in a common framework that addresses the general problem setting. Whereas it is impossible to give a strongly polynomial algorithm for the general problem even in an approximate sense (see Hochbaum [Math. Oper. Res., 19 (1994), pp. 390--409]), we show that assuming the existence of certain black-box oracles, one can give an algorithm using a strongly polynomial number of arithmetic operations and oracle calls only. The particular algorithms can be derived by implementing these oracles in the respective settings.

We consider connectivity-augmentation problems in a setting where each potential new edge has a non-negative cost associated with it, and the task is to achieve a certain connectivity target with at most p new edges of minimum total cost. The main result is that the minimum cost augmentation of edge-connectivity from k − 1 to k with at most p new edges is fixed-parameter tractable parameterized by p and admits a polynomial kernel. We also prove the fixed-parameter tractability of increasing edge connectivity from 0 to 2 and increasing node connectivity from 1 to 2.

We investigate problems addressing combined connectivity augmentation and orientations settings. We give a polynomial time 6-approximation algorithm for finding a minimum cost subgraph of an undirected graph G that admits an orientation covering a nonnegative crossing G-supermodular demand function, as defined by Frank [3]. An important example is (k,ℓ) -edge-connectivity, a common generalization of global and rooted edge-connectivity. Our algorithm is based on a non-standard application of the iterative rounding method. We observe that the standard linear program with cut constraints is not amenable and use an alternative linear program with partition and co-partition constraints instead. The proof requires a new type of uncrossing technique on partitions and co-partitions. We also consider the problem setting when the cost of an edge can be different for the two possible orientations. The problem becomes substantially more difficult already for the simpler requirement of k-edge-connectivity. Khanna, Naor and Shepherd [11] showed that the integrality gap of the natural linear program is at most 4 when k = 1 and conjectured that it is constant for all fixed k. We disprove this conjecture by showing an Ω(|V|) integrality gap even when k = 2.

A strongly polynomial algorithm is given for the generalized flow maximization problem. It uses a new variant of the scaling technique, called continuous scaling. The main measure of progress is that within a strongly polynomial number of steps, an arc can be identified that must be tight in every dual optimal solution, and thus can be contracted.

We present a 6-approximation algorithm for the minimum-cost $k$-node connected spanning subgraph problem, assuming that the number of nodes is at least $k^3(k-1)+k$. We apply a combinatorial preprocessing, based on the Frank--Tardos algorithm for $k$-outconnectivity, to transform any input into an instance such that the iterative rounding method gives a 2-approximation guarantee. This is the first constant factor approximation algorithm even in the asymptotic setting of the problem, that is, the restriction to instances where the number of nodes is lower bounded by a function of $k$.

We present a 6-approximation algorithm for the minimum-cost k-node connected spanning sub graph problem, assuming that the number of nodes is at least k3(k-1)+k. We apply a combinatorial preprocessing, based on the Frank-Tardos algorithm for k-out connectivity, to transform any input into an instance such that the iterative rounding method gives a 2-approximation guarantee. This is the first constant-factor approximation algorithm even in the asymptotic setting of the problem, that is, the restriction to instances where the number of nodes is lower bounded by a function of k.

The cutting plane approach to optimal matchings has been discussed by several authors over the past decades, and its rate of convergence has been an open question. We prove that the cutting plane approach using Edmonds' blossom inequalities converges in polynomial time for the minimum-cost perfect matching problem. Our main insight is an LP-based method to select cutting planes. This cut selection procedure leads to a sequence of intermediate linear programs with a linear number of constraints whose optima are half-integral and supported by a disjoint union of odd cycles and edges. This structural property of the optima is instrumental in finding violated blossom inequalities (cuts) in linear time. Moreover, the number of cycles in the support of the half-integral optima acts as a potential function to show efficient convergence to an integral solution.

We consider a nonlinear extension of the generalized network How model, with the How leaving an arc being an increasing concave function of the How entering it, as proposed by Truemper [1] and Shigeno [2]. We give a polynomial time combinatorial algorithm for solving corresponding How maximization problems, finding an ε-approximate solution in O(m(m + log n) log(MUm/ε)) arithmetic operations and value oracle queries, where M and U are upper bounds on simple parameters. This also gives a new algorithm for linear generalized Hows, an efficient, purely scaling variant of the Fat-Path algorithm by Goldberg, Plotkin and Tardos [3], not using any cycle cancellations. We show that this general convex programming model serves as a common framework for several market equilibrium problems, including the linear Fisher market model and its various extensions. Our result immediately provides combinatorial algorithms for various extensions of these market models. This includes nonsymmetric Arrow-Debreu Nash bargaining, settling an open question by Vazirani [4].

A well-studied nonlinear extension of the minimum-cost flow problem is to minimize the objective ∑ij∈E Cij(fij) over feasible flows f, where on every arc ij of the network, Cij is a convex function. We give a strongly polynomial algorithm for finding an exact optimal solution for a broad class of such problems. The key characteristic of this class is that an optimal solution can be computed exactly provided its support. This includes separable convex quadratic objectives and also certain market equilibria problems: Fisher's market with linear and with spending constraint utilities. We thereby give the first strongly polynomial algorithms for separable quadratic minimum-cost flows and for Fisher's market with spending constraint utilities, settling open questions posed e.g. in [15] and in [35], respectively. The running time is O(m4 log m) for quadratic costs, O(n4+n2(m+n log n) log n) for Fisher's markets with linear utilities and O(mn3 +m2(m+n log n) log m) for spending constraint utilities.

We present a min-max formula for the problem of augmenting the node-connectivity of a graph by one and give a polynomial time algorithm for finding an optimal solution. We also solve the minimum-cost version for node-induced cost functions.

We present a min-max formula for the problem of augmenting the node-connectivity of a graph by one and give a polynomial time algorithm for finding an optimal solution. We also solve the minimum cost version for node-induced cost functions.

In their seminal paper, Frank and Jordán [1995] show that a large class of optimization problems, including certain directed graph augmentation, fall into the class of covering supermodular functions over pairs of sets. They also give an algorithm for such problems, however, it relies on the ellipsoid method. Prior to our result, combinatorial algorithms existed only for the 0--1 valued problem. Our key result is a combinatorial algorithm for the general problem that includes directed vertex or S − T connectivity augmentation. The algorithm is based on Benczúr's previous algorithm for the 0--1 valued case [Benczúr 2003]. Our algorithm uses a primal-dual scheme for finding covers of partially ordered sets that satisfy natural abstract properties as in Frank and Jordán. For an initial (possibly greedy) cover, the algorithm searches for witnesses for the necessity of each element in the cover. If no two (weighted) witnesses have a common cover, the solution is optimal. As long as this is not the case, the witnesses are gradually exchanged for smaller ones. Each witness change defines an appropriate change in the solution; these changes are finally unwound in a shortest-path manner to obtain a solution of size one less.