Essays in Game Theory
In Honor of Michael Maschler
Article
The layered-step interior-point algorithm was introduced by Vavasis and Ye. The algorithm accelerates the path following interior-point algorithm and its arithmetic complexity depends only on the coefficient m...
Article
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 ...
Book
Chapter
The analogs of pure, mixed and behavior strategies in the context of algorithms are studied. It is shown that probabilistic machines are more powerful than probability distributions over deterministic ones, th...
Article
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
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
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...
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...
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...
Book
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
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
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
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
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...
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