A stronglypolynomial algorithm is given for the generalized flow maximization problem. It uses a new variant of the scaling technique, called continuous scaling. The main measure of progress is that within a strongly...
详细信息
ISBN:
(纸本)9781450327107
A stronglypolynomial algorithm is given for the generalized flow maximization problem. It uses a new variant of the scaling technique, called continuous scaling. The main measure of progress is that within a stronglypolynomial number of steps, an arc can be identified that must be tight in every dual optimal solution, and thus can be contracted.
Ye [2011] showed recently that the simplex method with Dantzig's pivoting rule, as well as Howard's policy iteration algorithm, solve discounted Markov decision processes (MDPs), with a constant discount facto...
详细信息
Ye [2011] showed recently that the simplex method with Dantzig's pivoting rule, as well as Howard's policy iteration algorithm, solve discounted Markov decision processes (MDPs), with a constant discount factor, in stronglypolynomial time. More precisely, Ye showed that both algorithms terminate after at most O (mn/1-gamma log n/1-gamma) iterations, where n is the number of states, m is the total number of actions in the MDP, and 0 < gamma < 1 is the discount factor. We improve Ye's analysis in two respects. First, we improve the bound given by Ye and show that Howard's policy iteration algorithm actually terminates after at most O(m/1-gamma log n/1-gamma) iterations. Second, and more importantly, we show that the same bound applies to the number of iterations performed by the strategy iteration (or strategy improvement) algorithm, a generalization of Howard's policy iteration algorithm used for solving 2-player turn-based stochastic games with discounted zero-sum rewards. This provides the first stronglypolynomial algorithm for solving these games, solving a long standing open problem. Combined with other recent results, this provides a complete characterization of the complexity the standard strategy iteration algorithm for 2-player turn-based stochastic games;it is stronglypolynomial for a fixed discount factor, and exponential otherwise.
A well-studied nonlinear extension of the minimum-cost flow problem is to minimize the objective E-ij is an element of E C-ij(f(ij)) over feasible flows f, where on every arc ij of the network, C-ij is a convex functi...
详细信息
ISBN:
(纸本)9781450312455
A well-studied nonlinear extension of the minimum-cost flow problem is to minimize the objective E-ij is an element of E C-ij(f(ij)) over feasible flows f, where on every arc ij of the network, C-ij is a convex function. We give a stronglypolynomial algorithm for finding an exact optimal solution for a broad class of such problems. The key characteristic of this class is that an optimal solution can be computed exactly provided its support. This includes separable convex quadratic objectives and also certain market equilibria problems: Fisher's market with linear and with spending constraint utilities. We thereby give the first strongly polynomial algorithms for separable quadratic minimum-cost flows and for Fisher's market with spending constraint utilities, settling open questions posed e.g. in [15] and in [35], respectively. The running time is O(m(4) log m) for quadratic costs, O(n(4)+n(2)(m+n log n) log n) for Fisher's markets with linear utilities and O(mn(3)+m(2)(m+ n log n) log m) for spending constraint utilities.
Inspired by the convex program of Eisenberg and Gale which captures Fisher markets with linear utilities, Jain and Vazirani [K. Jain and V. V. Vazirani, Games and Economic Behavior, 70 (2010), pp. 84-106] introduced t...
详细信息
Inspired by the convex program of Eisenberg and Gale which captures Fisher markets with linear utilities, Jain and Vazirani [K. Jain and V. V. Vazirani, Games and Economic Behavior, 70 (2010), pp. 84-106] introduced the class of Eisenberg-Gale (EG) markets. We study the structure of EG(2) markets, the class of EG markets with two agents. We prove that all markets in this class are rational, that is, they have rational equilibrium, and they admit stronglypolynomial time algorithms whenever the polytope containing the set of feasible utilities of the two agents can be described via a combinatorial linear program (LP). This helps positively resolve the status of two markets left as open problems by Jain and Vazirani: the capacity allocation market in a directed graph with two source-sink pairs and the network coding market in a directed network with two sources. Our algorithms for solving the corresponding nonlinear convex programs are fundamentally different from those obtained by Jain and Vazirani;whereas they use the primal-dual schema, our main tool is binary search powered by the strong LP-duality theorem.
In this paper, we consider the constrained inverse min-max spanning tree problems under the weighted Hamming distance. Three models are studied: the problem under the bottleneck-type weighted Hamming distance and two ...
详细信息
In this paper, we consider the constrained inverse min-max spanning tree problems under the weighted Hamming distance. Three models are studied: the problem under the bottleneck-type weighted Hamming distance and two mixed types of problems. We present their respective combinatorial algorithms that all run in stronglypolynomial times.
In this paper we show that the complexity of the simplex method for the linear fractional assignment problem (LFAP) is stronglypolynomial. Although LFAP can be solved in polynomial time using various algorithms such ...
详细信息
In this paper we show that the complexity of the simplex method for the linear fractional assignment problem (LFAP) is stronglypolynomial. Although LFAP can be solved in polynomial time using various algorithms such as Newton's method or binary search, no polynomial time bound for the simplex method for LFAP is known. (C) 2007 Elsevier B.V. All rights reserved.
The inverse optimization problem is to modify the weight (or cost, length, capacity and so on) such that a given feasible solution becomes an optimal solution. In this paper, we consider the inverse min-max spanning t...
详细信息
The inverse optimization problem is to modify the weight (or cost, length, capacity and so on) such that a given feasible solution becomes an optimal solution. In this paper, we consider the inverse min-max spanning tree problem under the weighted sum-type Hamming distance. For the model considered, we present its combinatorial algorithm that runs in stronglypolynomial times. (C) 2007 Elsevier B.V. All rights reserved.
Nonlinear optimization algorithms are rarely discussed from a complexity point of view. Even the concept of solving nonlinear problems on digital computers is not well defined. The focus here is on a complexity approa...
详细信息
Nonlinear optimization algorithms are rarely discussed from a complexity point of view. Even the concept of solving nonlinear problems on digital computers is not well defined. The focus here is on a complexity approach for designing and analyzing algorithms for nonlinear optimization problems providing optimal solutions with prespecified accuracy in the solution space. We delineate the complexity status of convex problems over network constraints, dual of flow constraints, dual of multi-commodity, constraints defined by a submodular rank function (a generalized allocation problem), tree networks, diagonal dominant matrices, and nonlinear knapsack problem's constraint. All these problems, except for the latter in integers, have polynomial time algorithms which may be viewed within a unifying framework of a proximity-scaling technique or a threshold technique. The complexity of many of these algorithms is furthermore best possible in that it matches lower bounds on the complexity of the respective problems. In general nonseparable optimization problems are shown to be considerably more difficult than separable problems. We compare the complexity of continuous versus discrete nonlinear problems and list some major open problems in the area of nonlinear optimization.
The inverse optimization problem is to modify the weight (or cost, length, capacity and so on) such that a given feasible solution becomes an optimal solution. In this paper, we consider the inverse min-max spanning t...
详细信息
ISBN:
(纸本)9783540744498
The inverse optimization problem is to modify the weight (or cost, length, capacity and so on) such that a given feasible solution becomes an optimal solution. In this paper, we consider the inverse min-max spanning tree problem under the weighted sum-type Hamming distance. For the model considered, we present its combinatorial algorithm that run in stronglypolynomial times.
In this paper, we consider inverse maximum flow problem under the weighted Hamming distance. Four models are studied: the problem under sum-type weighted Hamming distance;the problem under bottleneck-type weighted Ham...
详细信息
In this paper, we consider inverse maximum flow problem under the weighted Hamming distance. Four models are studied: the problem under sum-type weighted Hamming distance;the problem under bottleneck-type weighted Hamming distance and two mixed types of problems. We present their respective combinatorial algorithms that all run in stronglypolynomial times.
暂无评论