22 Result(s)
within
Article
Nimrod Megiddo
-
Article
The kernel and the nucleolus of a product of simple games
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
Optimal flows in networks with multiple sources and sinks
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
A monotone complementarity problem with feasible solutions but no complementary solutions
-
Article
On monotonicity in parametric linear complementarity problems
This paper generalizes the answers that were given by R.W. Cottle to questions that were originally raised by G. Maier.
-
Article
On the existence and uniqueness of solutions in nonlinear complementarity theory
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.
-
Article
Computing circular separability
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
On the expected number of linear complementarity cones intersected by random and semi-random rays
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
Improved asymptotic analysis of the average number of steps performed by the self-dual simplex algorithm
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
A note on degeneracy in linear programming
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
Introduction: New approaches to linear programming
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
On the complexity of polyhedral separability
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....
-
Article
Extending NC and RNC algorithms
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
On the ball spanned by balls
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,...
-
Article
An interior point potential reduction algorithm for the linear complementarity problem
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...
-
Article
Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality
The problem of integer programming in bounded variables, over constraints with no more than two variables in each constraint is NP-complete, even when all variables are binary. This paper deals with integer li...
-
Article
Theoretical convergence of large-step primal—dual interior point algorithms for linear programming
This paper proposes two sets of rules, Rule G and Rule P, for controlling step lengths in a generic primal—dual interior point method for solving the linear programming problem in standard form and its dual. T...
-
Article
A primal—dual infeasible-interior-point algorithm for linear programming
As in many primal—dual interior-point algorithms, a primal—dual infeasible-interior-point algorithm chooses a new point along the Newton direction towards a point on the central trajectory, but it does not con...
-
Article
New algorithms for generalized network flows
This paper, of which a preliminary version appeared in ISTCS'92, is concerned with generalized network flow problems. In a generalized network, each edgee = (u, v) has a positive ‘flow multiplier’a ...
-
Article
Algorithms and complexity analysis for some flow problems
Several network-flow problems with additional constraints are considered. They are all special cases of the linear-programming problem and are shown to be ℘-complete. It is shown that the existence of a strong...
-
Article
Finding mixed strategies with small supports in extensive form games
The complexity of algorithms that compute strategies or operate on them typically depends on the representation length of the strategies involved. One measure for thesize of a mixed strategy is the number of stra...
