Abstract We consider a market where a set of objects is sold to a set of buyers, each equipped with a valuation function for the objects. The goal of the auctioneer is to determine reasonable prices together with a stable allocation. One definition of “reasonable” and “stable” is a Walrasian equilibrium, which is a tuple consisting of a price vector together with an allocation satisfying the following desirable properties: (i) the allocation is market‐clearing in the sense that as much as possible is sold, and (ii) the allocation is stable in the sense that every buyer ends up with an optimal set with respect to the given prices. Moreover, “buyer‐optimal” means that the prices are smallest possible among all Walrasian prices. In this paper, we present a combinatorial network flow algorithm to compute buyer‐optimal Walrasian prices in a multi‐unit matching market with truncated additive valuation functions. The algorithm can be seen as a generalization of the classical housing market auction and mimics the very natural procedure of an ascending auction. We use our structural insights to prove monotonicity of the buyer‐optimal Walrasian prices with respect to changes in supply or demand.

In this note we give a polynomial time algorithm for solving the closest vector problem in the class of zonotopal lattices. The Voronoi cell of a zonotopal lattice is a zonotope, i.e., a projection of a regular cube. Examples of zonotopal lattices include lattices of Voronoi's first kind and tensor products of root lattices of type $\mathsf{A}$. The combinatorial structure of zonotopal lattices can be described by regular matroids/totally unimodular matrices. We observe that a linear algebra version of the minimum mean cycle canceling method can be applied for efficiently solving the closest vector problem in a zonotopal lattice if the lattice is given as the integral kernel of a totally unimodular matrix.

We introduce reroutable flows, a robust version of network flows in which link failures can be mitigated by rerouting the affected flow. An important new feature of this model, distinguishing it from existing robust network flow models, is that no flow can get lost in the network. Our goal is to compute maximum flows under this robustness requirement. We investigate different variants depending on the number of failing links, the capacities available for rerouting, and integrality requirements. While the most general versions of the model turn out to be $NP$-hard, we devise linear programming (LP) formulations and combinatorial algorithms for important special cases and provide approximation algorithms for the harder variants.

This paper presents a new strongly polynomial cut canceling algorithm for minimum cost submodular flow. The algorithm is a generalization of our similar cut canceling algorithm for ordinary min-cost flow. The algorithm scales a relaxed optimality parameter and creates a second, inner relaxation that is a kind of submodular max flow problem. The outer relaxation uses a novel technique for relaxing the submodular constraints that allows our previous proof techniques to work. The algorithm uses the min cuts from the max flow subproblem as the relaxed most positive cuts it chooses to cancel. We show that this algorithm needs to cancel only ${\mathrm O}(n^3)$ cuts per scaling phase, where n is the number of nodes. Furthermore, we show how to slightly modify this algorithm to get a strongly polynomial running time. Finally, we briefly show how to extend this algorithm to the separable convex cost case and that the same technique can be used to construct a polynomial time maximum mean cut canceling algorithm for submodular flow.

We consider the problem of minimizing a separable convex objective function over the linear space given by a system Mx=0 with M a totally unimodular matrix. In particular, this generalizes the usual minimum linear cost circulation and cocirculation problems in a network and the problems of determining the Euclidean distance from a point to the perfect bipartite matching polytope and the feasible flows polyhedron. We first show that the idea of minimum mean cycle canceling originally worked out for linear cost circulations by Goldberg and Tarjan [J. Assoc. Comput. Mach., 36 (1989), pp. 873--886.] and extended to some other problems [T. R. Ervolina and S. T. McCormick, Discrete Appl. Math., 46 (1993), pp. 133--165], [A. Frank and A. V. Karzanov, Technical Report RR 895-M, Laboratoire ARTEMIS IMAG, Université Joseph Fourier, Grenoble, France, 1992], [T. Ibaraki, A. V. Karzanov, and H. Nagamochi, private communication, 1993], [M. Hadjiat, Technical Report, Groupe Intelligence Artificielle, Faculté des Sciences de Luminy, Marseille, France, 1994] can be generalized to give a combinatorial method with geometric convergence for our problem. We also generalize the computationally more efficient cancel-and-tighten method. We then consider objective functions that are piecewise linear, pure and piecewise quadratic, or piecewise mixed linear and quadratic, and we show how both methods can be implemented to find exact solutions in polynomial time (strongly polynomial in the piecewise linear case). These implementations are then further specialized for finding circulations and cocirculations in a network. We finish by showing how to extend our methods to find optimal integer solutions, to linear spaces of larger fractionality, and to the case when the objective functions are given by approximate oracles.

Chen [3] develops an attractive variant of the classical prob lem of preemptively scheduling independent jobs with r~ lease dates and due datea.Chen suggests that in practice one can often pay to reduce the processing requirement of a job.This leads to two parametric max flow problems.Seraiini [14] considers scheduling independent jobs with due dates on multiple machines, where jobs can be split among machines so that pieces of a single job can execute in parallel.Minimta" ing the maximum tardiness again gives a para- metric max flow problem.A third problem of th~type is deciding how many more games a baseball team can lose partway through a seaeon without being eliminated from finishing first.A fourth such problem is an extended selection problem of Brumelle, Granot, and Liu [2], where we want to discount the costs of 'tree-struct ured~tools as little as possible to be able to process all jobs at a profit.It is tempting to try to solve these problems with the parametric push-relabel max flow methods of Gallo, Griganadis and Tarjatt (GGT) [6].However, all of these applications appear to violate the conditions necessary to apply GGT.We extend GGT in three ways which allow it to be applied to all four of the above applications.Our extensions to GGT yield f~ter algorithms for all these applications.

We consider the problem of scheduling n jobs without precedence constraints on m uniform machines (i.e., the machines are identical except for speed), with preemptions allowed at no cost. We are interested in generating the entire tradeoff curve of schedules which are Pareto-optimal (undominated) for the flowtime and makespan objectives. To achieve this, we first develop an O(mn) algorithm that produces a schedule with minimum flowtime, subject to a fixed makespan deadline. This algorithm alternates between the Shortest Processing Time on Fastest Machine (SPT-FM) rule and the Longest Remaining Processing Time on Fastest Machine (LRPT-FM) rule. We then investigate how the behavior of the algorithm changes as the deadline is varied parametrically. Our knowledge of the structure of optimal schedules allows us to characterize breakpoints on the (piecewise linear) tradeoff curve, and then to compute all of the O(mn) breakpoints in O(m3n) time. Our analysis yields various useful sensitivity results as a by-product. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

Abstract We present a polynomial algorithm for the minimum cost network flow problem (MCNF). It is a dual algorithm that is based on canceling positive augmenting cuts, which are the duals of negative augmenting cycles. We focus on canceling most helpful total cuts , which are cuts together with augmentation amounts that lead to the maximum possible increase in the dual objective function. We show how to compute a most helpful total cut and give a rigorous dual conformal decomposition theorem. Canceling most helpful cuts is, in spirit, dual to an algorithm of Weintraub as modified by Barahona and Tardos. We also show how our algorithm specializes to the case of shortest s–t path with nonnegative distances, show that this specialization is not finite for real data, and show that our bound on the number of cancellations is essentially tight. © 1993 by John Wiley & Sons, Inc.

Many optimization algorithms involve repeated processing of a fixed set of linear constraints. If the constraint matrix A is preprocessed to make it sparser, algebraic operations should become faster. In many applications there is a priori information about the likelihood that each column will appear in a basis, which can be expressed as weights on the columns. This leads to considering the weighted sparsity problem (WSP): Find a row-equivalent constraint matrix with as small a weight of nonzeros as possible. The WSP is shown to be NP-hard even with a nondegeneracy assumption, and even if restricted to instances with at most three nonzeros per both row and column. WSP is shown to have a polynomial algorithm when the number of nonzeros per either row or column is limited to at most two. This contrasts with previous results that, assuming only nondegeneracy, the unweighted version of WSP does have a polynomial algorithm (this has proven to be practically useful in tests on real data). The polynomial algorithm for WSP with at most two nonzeros per row or column is based on solving one-row problems via minimum cut calculations, together with a sufficient condition for piecing these one-row solutions together into a global solution.

If A is the (sparse) coefficient matrix of linear-equality constraints, for what nonsingular T is A = TA as sparse as possible, and how can it be efficiently computed? An efficient algorithm for this Sparsity Problem (SP) would be a valuable preprocessor for linearly constrained optimization problems. In a companion paper we developed a two-pass approach to solve SP called the Hierarchical Algorithm . In this paper we report on how we implemented the Hierarchical Algorithm into a code called HASP, and our computational experience in testing HASP on the NETLIB linear-programming problems. We found that HASP substantially outperformed a previous code for SP and that it produced a net savings in optimization time on the NETLIB problems. The results allow us to give guidelines for its use in practice.

Abstract Consider a network G = (V,E) with distinguished vertices s and t, and with k different costs on every edge. We consider the problem of finding k disjoint paths from s to t such that the total cost of the paths is minimized, where the jth edge‐cost is associated with the jth path. The problem has several variants: The paths may be vertex‐disjoint or arc‐disjoint and the network may be directed or undirected. We show that all four versions of the problem are strongly NP‐complete even for k = 2. We describe polynomial time heuristics for the problem and a polynomial time algorithm for the acyclic directed case.