Progress in Mathematical Programming
Interior-Point and Related Methods
Article
The kernel and the nucleolus of a product of two simple games are given in terms of the kernels and the nucleoluses of the component games.
Article
The concept of an optimal flow in a multiple source, multiple sink network is defined. It generalizes maximal flow in a single source, single sink network. An existence proof and an algorithm are given.
Article
Article
This paper generalizes the answers that were given by R.W. Cottle to questions that were originally raised by G. Maier.
Article
A complementarity problem is said to be globally uniquely solvable (GUS) if it has a unique solution, and this property will not change, even if any constant term is added to the map** generating the problem.
Chapter
A parametrized version of the nonlinear complementarity problem is formulated. The existence of a continuation of a solution is investigated and sufficient and necessary conditions for the monotonicity of such...
Article
Two sets of planar pointsS 1 andS 2 are circularly separable if there is a circle that enclosesS 1 but excludesS 2. We show that deciding whether two sets are circularly separable can be accomplished inO(n) time ...
Article
Lemke's algorithm for the linear complementarity problem follows a ray which leads from a certain fixed point (traditionally, the point (1,⋯, 1)T) to the point given in the problem. The problem also induces a set...
Article
In this paper we analyze the average number of steps performed by the self-dual simplex algorithm for linear programming, under the probabilistic model of spherical symmetry. The model was proposed by Smale. C...
Article
We show that the problem of exiting a degenerate vertex is as hard as the general linear programming problem. More precisely, every linear programming problem can easily be reduced to one where the second best...
Article
This issue ofAlgorithmica present papers on various aspects of nonlinear methods for solving linear programming problems, inspired by the work of Karmarkar. This introduction describes some of these aspects and b...
Article
It is NP-complete to recognize whether two sets of points in general space can be separated by two hyperplanes. It is NP-complete to recognize whether two sets of points in the plane can be separated withk lines....
Book
Chapter
This chapter presents continuous paths leading to the set of optimal solutions of a linear programming problem. These paths are derived from the weighted logarithmic barrier function. The defining equations ar...
Article
A technique is presented by which NC and RNC algorithms for some problems can be extended into NC and RNC algorithms, respectively, that solve more general parametric problems. The technique is demonstrated on...
Article
The procedure for linear programming in linear time in fixed dimension is extended to solve in linear time certain nonlinear problems. Examples are the problem of finding the smallest ball enclosingn given balls,...
Book
Chapter and Conference Paper
This paper is concerned with generalized network flow problems. In a generalized network, each edge e=(u, v) has a positive “flow multiplier” a e associated with it. The interpretation is that if a flow of x e en...
Article
The linear complementarity problem (LCP) can be viewed as the problem of minimizingx T y subject toy=Mx+q andx, y⩾0. We are interested in finding a point withx T y <ε for a givenε > 0. The algorithm proceeds by i...
Chapter
Blum, Shub, and Smale [2] formalized a model of computation over a general ring. They proved an analogue of Cook’s theorem [3] over the reals. Smale [4] has recently raised the question of existence of NP-comp...