An algorithm for linear programming which requires O(((m+n)n 2+(m+n)1.5 n)L) arithmetic operations

We present an algorithm for linear programming which requires O(((m+n)n ²+(m+n)^1.5 n)L) arithmetic operations wherem is the number of constraints, andn is the number of variables. Each operation is performed to a precision of O(L) bits.L is bounded by the number of bits in the input. The worst-case running time of the algorithm is better than that of Karmarkar's algorithm by a factor of .     

An extension of Karmarkar's projective algorithm for convex quadratic programming

We present an extension of Karmarkar's linear programming algorithm for solving a more general group of optimization problems: convex quadratic programs. This extension is based on the iterated application of the objective augmentation and the projective transformation, followed by optimization over an inscribing ellipsoid centered at the current solution. It creates a sequence of interior feasible points that converge to the optimal feasible solution in O(Ln) iterations; each iteration can be computed in O(Ln ³) arithmetic operations, wheren is the number of variables andL is the number of bits in the input. In this paper, we emphasize its convergence property, practical efficiency, and relation to the ellipsoid method.     

A randomized scheme for speeding up algorithms for linear and convex programming problems with high constraints-to-variables ratio

We extend Clarkson's randomized algorithm for linear programming to a general scheme for solving convex optimization problems. The scheme can be used to speed up existing algorithms on problems which have many more constraints than variables. In particular, we give a randomized algorithm for solving convex quadratic and linear programs, which uses that scheme together with a variant of Karmarkar's interior point method. For problems withn constraints,d variables, and input lengthL, ifn = (d ²), the expected total number of major Karmarkar's iterations is O(d ²(logn)L), compared to the best known deterministic bound of O( L). We also present several other results which follow from the general scheme.     

A new polynomial-time algorithm for linear programming

We present a new polynomial-time algorithm for linear programming. In the worst case, the algorithm requiresO(n ^3.5 L) arithmetic operations onO(L) bit numbers, wheren is the number of variables andL is the number of bits in the input. The running-time of this algorithm is better than the ellipsoid algorithm by a factor ofO(n ^2.5). We prove that given a polytopeP and a strictly interior point a εP, there is a projective transformation of the space that mapsP, a toP′, a′ having the following property. The ratio of the radius of the smallest sphere with center a′, containingP′ to the radius of the largest sphere with center a′ contained inP′ isO(n). The algorithm consists of repeated application of such projective transformations each followed by optimization over an inscribed sphere to create a sequence of points which converges to the optimal solution in polynomial time. This is a substantially revised version of the paper presented at the Symposium on Theory of Computing, Washington D. C., April 1984.     

Relaxed variants of Karmarkar's algorithm for linear programs with unknown optimal objective value

Variants of Karmarkar's algorithm are given for solving linear programs with unknown optimal objective valuez ^*. These new methods combine the approach of Goldfarb and Mehrotra for relaxing the requirement that certain projections be computed exactly with the approach of Todd and Burrell for generating an improving sequence of lower bounds forz ^* using dual feasible solutions. These methods retain the polynomial-time complexity of Karmarkar's algorithm.This research was supported in part by NSF Grants DMS-85-12277 and CDR-84-21402, and ONR Contract N0014-87-K0214.     

An extension of Karmarkar's algorithm for solving a system of linear homogeneous equations on the simplex

We present an extension of Karmarkar's algorithm for solving a system of linear homogeneous equations on the simplex. It is shown that in at most O(nL) steps, the algorithm produces a feasible point or proves that the problem has no solution. The complexity is O(n ² m ² L) arithmetic operations. The algorithm is endowed with two new powerful stopping criteria.     

An approximate max-flow min-cut relation for undirected multicommodity flow,with applications

In this paper, we prove the first approximate max-flow min-cut theorem for undirected multicommodity flow. We show that for a feasible flow to exist in a multicommodity problem, it is sufficient that every cut's capacity exceeds its demand by a factor ofO(logClogD), whereC is the sum of all finite capacities andD is the sum of demands. Moreover, our theorem yields an algorithm for finding a cut that is approximately minimumrelative to the flow that must cross it. We use this result to obtain an approximation algorithm for T. C. Hu's generalization of the multiway-cut problem. This algorithm can in turn be applied to obtain approximation algorithms for minimum deletion of clauses of a 2-CNF formula, via minimization, and other problems. We also generalize the theorem to hypergraph networks; using this generalization, we can handle CNF clauses with an arbitrary number of literals per clause.Most of the results in this paper were presented in preliminary form in Approximation through multicommodity flow,Proceedings, 31th Annual Symposium on Foundations of Computer Science (1990), pp. 726–737.Research supported by the National Science Foundation under NSF grant CDA 8722809, by the Office of Naval and the Defense Advanced Research Projects Agency under contract N00014-83-K-0146, and ARPA Order No. 6320, Amendament 1.Research supported by NSF grant CCR-9012357 and by an NSF Presidential Young Investigator Award.     

A simplified homogeneous and self-dual linear programming algorithm and its implementation

We present a simplification and generalization of the recent homogeneous and self-dual linear programming (LP) algorithm. The algorithm does not use any Big-M initial point and achieves -iteration complexity, wheren andL are the number of variables and the length of data of the LP problem. It also detects LP infeasibility based on a provable criterion. Its preliminary implementation with a simple predictor and corrector technique results in an efficient computer code in practice. In contrast to other interior-point methods, our code solves NETLIB problems, feasible or infeasible, starting simply fromx=e (primal variables),y=0 (dual variables),z=e (dual slack variables), wheree is the vector of all ones. We describe our computational experience in solving these problems, and compare our results with OB1.60, a state-of-the-art implementation of interior-point algorithms.Research supported in part by NSF Grant DDM-9207347 and by an Iowa College of Business Administration Summer Grant.Part of this work was done while the author was on a sabbatical leave from the University of Iowa and visiting the Cornell Theory Center, Cornell University, Ithaca, NY 14853, USA, supported in part by the Cornell Center for Applied Mathematics and by the Advanced Computing Research Institute, a unit of the Cornell Theory Center, which receives major funding from the National Science Foundation and IBM Corporation, with additional support from New York State and members of its Corporate Research Institute.     

Metrics and undirected cuts

Suppose thatG is an undirected graph whose edges have nonnegative integer-valued lengthsl(e), and that {s ₁,t ₁},?, {s _m ,t _m } are pairs of its vertices. Can one assign nonnegative weights to the cuts ofG such that, for each edgee, the total weight of cuts containinge does not exceedl(e) and, for eachi, the total weight of cuts ‘separating’s _i andt _i is equal to the distance (with respect tol) betweens _i andt _i ? Using linear programming duality, it follows from Papernov's multicommodity flow theorem that the answer is affirmative if the graph induced by the pairs {s ₁,t ₁},?, {s _m ,t _m } is one of the following: (i) the complete graph with four vertices, (ii) the circuit with five vertices, (iii) a union of two stars. We prove that if, in addition, each circuit inG has an even length (with respect tol) then there exists a suitable weighting of the cuts with the weights integer-valued; moreover, an algorithm of complexity O(n ³) (n is the number of vertices ofG) is developed for solving such a problem. Also a class of metrics decomposable into a nonnegative linear combination of cut-metrics is described, and it is shown that the separation problem for cut cones isNP-hard.     

An O(n 3 L) primal—dual potential reduction algorithm for solving convex quadratic programs

In this paper we combine partial updating and an adaptation of Anstreicher's safeguarded linesearch of the primal—dual potential function with Kojima, Mizuno and Yoshise's potential reduction algorithm for the linear complementarity problem to obtain an O(n ³ L) algorithm for convex quadratic programming. Our modified algorithm is a long step method that requires at most O( L) steps.This research was supported in part by ONR Contract N-00014-87-K0214, NSF Grants DMS-85-12277 and DMS-91-06195.     

An interior point method, based on rank-1 updates, for linear programming

We propose a polynomial time primal—dual potential reduction algorithm for linear programming. The algorithm generates sequencesd ^k andv ^k rather than a primal—dual interior point (x ^k ,s ^k ), where and fori = 1, 2,,n. Only one element ofd ^k is changed in each iteration, so that the work per iteration is bounded by O(mn) using rank-1 updating techniques. The usual primal—dual iteratesx ^k ands ^k are not needed explicitly in the algorithm, whereasd ^k andv ^k are iterated so that the interior primal—dual solutions can always be recovered by aforementioned relations between (x ^k, s^k) and (d ^k, v^k) with improving primal—dual potential function values. Moreover, no approximation ofd ^k is needed in the computation of projection directions. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.     

On Anstreicher's combined phase I—phase II projective algorithm for linear programming

Anstreicher has proposed a variant of Karmarkar's projective algorithm that handles standard-form linear programming problems nicely. We suggest modifications to his method that we suspect will lead to better search directions and a more useful algorithm. Much of the analysis depends on a two-constraint linear programming problem that is a relaxation of the scaled original problem.Research supported in part by NSF Grant ECS-8602534 and ONR Contract N00014-87-K-0212.     

An O(n 3 L) adaptive path following algorithm for a linear complementarity problem

In this paper we propose an O(n ³ L) algorithm which is a modification of the path following algorithm [8] for a linear complementarity problem. The path following algorithm has to take a short step size in each iteration in order to bound the number of overall arithmetic operations by O(n ³ L). In practical computation, we can determine the step size adaptively. Mizuno, Yoshise, and Kikuchi [11] reported that such an adaptive algorithm required about O(L) iterations for some test problems. Here we show that we can use a rank one update technique in the adaptive algorithm so that the number of overall arithmetic operations is theoretically bounded by O(n ³ L).Research supported in part by the U.S. Army Research Office through the Mathematical Sciences Institute of Cornell University.Research supported in part by NSF grants ECS-8602534 and DMS-8904406 and ONR contract N-00014-87-K0212.     

Finite element approximation of the volume-matching problem

Summary Optimal orderH ¹ andL error bounds are obtained for a continuous piecewise linear finite element approximation of the volume matching problem. This problem consists of minimising |v| _1, ² overvH ¹() subject to the inequality constraintv0 and a number of linear equality constraints. The presence of the equality constraints leads to Lagrange multipliers, which in turn lead to complications with the standard error analysis for variational inequalities. Finally we consider an algorithm for solving the resulting algebraic problem.Supported by a SERC research studentship     

On the comparison of PBIB designs with two associate classes

A method to compare two-associate-class PBIB designs is discussed. As an application, it is shown that ifd ^* is a group-divisible design withλ ₂=λ₁+1, a group divisible design with group size two andλ ₂=λ₁+1>1, a design based on a triangular scheme andv=10 andλ ₁=λ₂+1, a design with anL ₂ scheme andλ ₂=λ₁+1, a design with anL _s scheme,v=(s+1) ², andλ ₂=λ₁+1, wheres is a positive integer, or a design with a cyclic schemev=5, andλ ₁=λ₂±1, thend ^* is optimum with respect to a very general class of criteria over all the two-associate-class PBIB designs with the same values ofv, b andk asd ^*. The best two-associate-class PBIB design, however, is not necessarily optimal over all designs. This paper was prepared with the support of Office of Naval Research Contract No. N00014-75-C-0444/NR 042-036 and National Science Foundation Grant No. MCS-79-09502.     

有预算限制的最大多种物资流问题

研究有预算限制的最大多种物资流问题,给出了这个问题的不依赖物资数k的全多项式时间近似算法,其算法复杂性是O~(-ε2m2).同时,利用有预算限制的最大多种物资流问题的研究结果,我们也得到了费用最小的最大多种物资流问题的近似算法和算法复杂性.     

Fast deterministic approximation for the multicommodity flow problem

In this paper we consider an optimization version of the multicommodity flow problem which is known as the maximum concurrent flow problem. We show that an approximate solution to this problem can be computed deterministically using O(k(ε ⁻² + logk) logn) 1-commodity minimum-cost flow computations, wherek is the number of commodities,n is the number of nodes, andε is the desired precision. We obtain this bound by proving that in the randomized algorithm developed by Leighton et al. (1995) the random selection of commodities can be replaced by the deterministic round-robin without increasing the total running time. Our bound significantly improves the previously known deterministic upper bounds and matches the best known randomized upper bound for the approximation concurrent flow problem. A preliminary version of this paper appeared inProceedings of the 6th ACM-SIAM Symposium on Discrete Algorithms, San Francisco CA, 1995, pp. 486–492.     

Finding an interior point in the optimal face of linear programs

We study the problem of finding a point in the relative interior of the optimal face of a linear program. We prove that in the worst case such a point can be obtained in O(n ³ L) arithmetic operations. This complexity is the same as the complexity for solving a linear program. We also show how to find such a point in practice. We report and discuss computational results obtained for the linear programming problems in the NETLIB test set.Research supported in part by NSF Grant CCR-8810107, CCR-9019469 and a grant from GTE Laboratories.Research supported in part by NSF Grant DDM-8922636 and NSF Coop. Agr. No. CCR-8809615 through Rice University.     

Facet-reducing cuts of a convex polytope

We construct, for everyd>-4, ad-polytopeP⊂ℝ ^d , containing two verticesv andw such that no hyperplane of ℝ ^d containingv andw has more than one facet ofP in either of its closed half-spaces. The result shows that facet-reducing cuts containing a prespecified pair of vertices of a polytope, do not exist in general. This research was supported in part by an NSF Research Initiation Award.     

A primal—dual potential reduction method for problems involving matrix inequalities

We describe a potential reduction method for convex optimization problems involving matrix inequalities. The method is based on the theory developed by Nesterov and Nemirovsky and generalizes Gonzaga and Todd's method for linear programming. A worst-case analysis shows that the number of iterations grows as the square root of the problem size, but in practice it appears to grow more slowly. As in other interior-point methods the overall computational effort is therefore dominated by the least-squares system that must be solved in each iteration. A type of conjugate-gradient algorithm can be used for this purpose, which results in important savings for two reasons. First, it allows us to take advantage of the special structure the problems often have (e.g., Lyapunov or algebraic Riccati inequalities). Second, we show that the polynomial bound on the number of iterations remains valid even if the conjugate-gradient algorithm is not run until completion, which in practice can greatly reduce the computational effort per iteration.We describe in detail how the algorithm works for optimization problems withL Lyapunov inequalities, each of sizem. We prove an overallworst-case operation count of O(m ^5.5L^1.5). Theaverage-case complexity appears to be closer to O(m ⁴L^1.5). This estimate is justified by extensive numerical experimentation, and is consistent with other researchers' experience with the practical performance of interior-point algorithms for linear programming.This result means that the computational cost of extending current control theory based on the solution of Lyapunov or Riccatiequations to a theory that is based on the solution of (multiple, coupled) Lyapunov or Riccatiinequalities is modest.Supported by the Belgian National Fund for Scientific Research (NFWO). Research supported in part by the Belgian program on Interuniversity Attraction Poles (IUAP 17 and 50) initiated by the Belgian State, Prime Minister's Office, Science Policy Programming.Research supported in part by AFOSR (under F49620-92-J-0013), NSF (under ECS-9222391) and ARPA (under F49620-93-1-0085).