We consider integer and linear programming problems for which the linear constraints exhibit a (recursive) block-structure: The problem decomposes into independent and efficiently solvable sub-problems if a small number of constraints is deleted. A prominent example are n-fold integer programming problems and their generalizations which have received considerable attention in the recent literature. The previously known algorithms for these problems are based on the augmentation framework, a tailored integer programming variant of local search. In this paper we propose a different approach. Our algorithm relies on parametric search and a new proximity bound. We show that block-structured linear programming can be solved efficiently via an adaptation of a parametric search framework by Norton, Plotkin, and Tardos in combination with Megiddo's multidimensional search technique. This also forms a subroutine of our algorithm for the integer programming case by solving a strong relaxation of it. Then we show that, for any given optimal vertex solution of this relaxation, there is an optimal integer solution within ℓ1-distance independent of the dimension of the problem. This in turn allows us to find an optimal integer solution efficiently. We apply our techniques to integer and linear programming with n-fold structure or bounded dual treedepth, two benchmark problems in this field. We obtain the first algorithms for these cases that are both near-linear in the dimension of the problem and strongly polynomial. Moreover, unlike the augmentation algorithms, our approach is highly parallelizable.

We present a factor 4/3 approximation algorithm for the problem of finding a minimum 2-edge connected spanning subgraph of a given undirected multigraph. The algorithm is based upon a reduction to a restricted class of graphs. In these graphs, the approximation algorithm constructs a 2-edge connected spanning subgraph by modifying the smallest 2-edge cover.

We consider integer programming problems max {c^Tx : A x = b, l <= x <= u, x in Z^{nt}} where A has a (recursive) block-structure generalizing n-fold integer programs which recently received considerable attention in the literature. An n-fold IP is an integer program where A consists of n repetitions of submatrices A in Z^{r × t} on the top horizontal part and n repetitions of a matrix B in Z^{s × t} on the diagonal below the top part. Instead of allowing only two types of block matrices, one for the horizontal line and one for the diagonal, we generalize the n-fold setting to allow for arbitrary matrices in every block. We show that such an integer program can be solved in time n^2t^2 phi x (r s delta)^{O(rs^2+ sr^2)} (ignoring logarithmic factors). Here delta is an upper bound on the largest absolute value of an entry of A and phi is the largest binary encoding length of a coefficient of c. This improves upon the previously best algorithm of Hemmecke, Onn and Romanchuk that runs in time n^3t^3 phi x delta^{O(st(r+t))}. In particular, our algorithm is not exponential in the number t of columns of A and B. Our algorithm is based on a new upper bound on the l_1-norm of an element of the Graver basis of an integer matrix and on a proximity bound between the LP and IP optimal solutions tailored for IPs with block structure. These new bounds rely on the Steinitz Lemma. Furthermore, we extend our techniques to the recently introduced tree-fold IPs, where we again present a more efficient algorithm in a generalized setting.

Since the 1990s spectrum auctions have been implemented world-wide. This has provided for a practical examination of an assortment of auction mechanisms and, amongst these, two simultaneous ascending price auctions have proved to be extremely successful. These are the simultaneous multiround ascending auction (SMRA) and the combinatorial clock auction (CCA). It has long been known that, for certain classes of valuation functions, the SMRA provides good theoretical guarantees on social welfare. However, no such guarantees were known for the CCA. In this paper, we show that CCA does provide strong guarantees on social welfare provided the price increment and stopping rule are well-chosen. This is very surprising in that the choice of price increment has been used primarily to adjust auction duration and the stopping rule has attracted little attention. The main result is a polylogarithmic approximation guarantee for social welfare when the maximum number of items demanded by a bidder is fixed. Specifically, we show that either the revenue of the CCA is at least an -fraction of the optimal welfare or the welfare of the CCA is at least an -fraction of the optimal welfare, where n is the number of bidders and m is the number of items. As a corollary, the welfare ratio – the worst case ratio between the social welfare of the optimum allocation and the social welfare of the CCA allocation – is at most O( 2 · log n·· log2 m). We emphasize that this latter result requires no assumption on bidders valuation functions. Finally, we prove that such a dependence on is necessary. In particular, we show that the welfare ratio of the CCA is at least .