-
作者：Asmussen, Soren; Fiorini, Pierre; Lipsky, Lester; Rolski, Tomasz; Sheahan, Robert
作者单位：Aarhus University; University of Maine System; University of Southern Maine; University of Connecticut; University of Wroclaw
摘要：Many processes must complete in the presence of failures. Different systems respond to task failure in different ways. The system may resume a failed task from the failure point (or a saved checkpoint shortly before the failure point), it may give up on the task and select a replacement task from the ready queue, or it may restart the task. The behavior of systems under the first two scenarios is well documented, but the third (RESTART) has resisted detailed analysis. In this paper we derive t...
-
作者：Benoit, Genevieve; Boyd, Sylvia
作者单位：University of Ottawa
摘要：The symmetric traveling salesman problem (STSP) is to find a minimum weight Hamiltonian cycle in a weighted complete graph on n nodes. One direction which seems promising for finding improved solutions for the STSP is the study of a linear relaxation of this problem called the subtour elimination problem (SEP). A well-known conjecture in combinatorial optimization says that the integrality gap of the SEP is 4/3 in the metric case. Finding the exact value for this integrality gap is challenging...
-
作者：Dunkel, Juliane; Schulz, Andreas S.
作者单位：Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT)
摘要：Rosenthal's congestion games constitute one of the few known classes of noncooperative games possessing pure-strategy Nash equilibria. In the network version, each player wants to route one unit of flow on a single path from her origin to her destination at minimum cost, and the cost of using an arc depends only on the total number of players using that arc. A natural extension is to allow for players controlling different amounts of flow, which results in so-called weighted congestion games. ...
-
作者：Dean, Brian C.; Goemans, Michel X.; Vondrak, Jan
作者单位：Massachusetts Institute of Technology (MIT)
摘要：We consider a stochastic variant of the NP-hard 0/1 knapsack problem, in which item values are deterministic and item sizes are independent random variables with known, arbitrary distributions. Items are placed in the knapsack sequentially, and the act of placing an item in the knapsack instantiates its size. Our goal is to compute a solution policy that maximizes the expected value of items successfully placed in the knapsack, where the final over. owing item contributes no value. We consider...
-
作者：So, Anthony Man-Cho; Ye, Yinyu; Zhang, Jiawei
作者单位：Chinese University of Hong Kong; Stanford University; New York University
摘要：We consider the problem of finding a low-rank approximate solution to a system of linear equations in symmetric, positive semidefinite matrices, where the approximation quality of a solution is measured by its maximum relative deviation, both above and below, from the prescribed quantities. We show that a simple randomized polynomial-time procedure produces a low-rank solution that has provably good approximation qualities. Our result provides a unified treatment of and generalizes several wel...
-
作者：Vladimirsky, Alexander
作者单位：Cornell University
摘要：Stochastic shortest path (SSP) problems arise in a variety of discrete stochastic control contexts. An optimal solution to such a problem is typically computed using the value function, which can be found by solving the corresponding dynamic programming equations. In the deterministic case, these equations can be often solved by highly efficient label-setting methods (such as Dijkstra's and Dial's algorithms). In this paper we de. ne and study a class of multimode stochastic shortest path (MSS...
-
作者：Eisenbrand, Friedrich; Shmonin, Gennady
作者单位：Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne
摘要：Parametric integer programming deals with a family of integer programs that is defined by the same constraint matrix but where the right-hand sides are points of a given polyhedron. The question is whether all these integer programs are feasible. Kannan showed that this can be checked in polynomial time if the number of variables in the integer programs is fixed and the polyhedron of right-hand sides has fixed affine dimension. In this paper, we extend this result by providing a polynomial alg...
-
作者：Basu, Arnab; Bhattacharyya, Tirthankar; Borkar, Vivek S.
作者单位：Indian Institute of Management (IIM System); Indian Institute of Management Bangalore; Indian Institute of Science (IISC) - Bangalore; Tata Institute of Fundamental Research (TIFR)
摘要：A linear function approximation-based reinforcement learning algorithm is proposed for Markov decision processes with infinite horizon risk-sensitive cost. Its convergence is proved using the o.d.e. method for stochastic approximation. The scheme is also extended to continuous state space processes.
-
作者：von Stengel, Bernhard; Forges, Francoise
作者单位：University of London; London School Economics & Political Science; Universite PSL; Universite Paris-Dauphine
摘要：This paper defines the extensive-form correlated equilibrium (EFCE) for extensive games with perfect recall. The EFCE concept extends Aumann's strategic-form correlated equilibrium (CE). Before the game starts, a correlation device generates a move for each information set. This move is recommended to the player only when the player reaches the information set. In two-player perfect-recall extensive games without chance moves, the set of EFCE can be described by a polynomial number of consiste...
-
作者：Aldous, David J.
作者单位：University of California System; University of California Berkeley
摘要：In a network where the cost of flow across an edge is nonlinear in the volume of flow, and where sources and destinations are uniform, one can consider the relationship between total volume of flow through the network and the minimum cost of any flow with given volume. Under a simple probability model (locally tree-like directed network, independent cost-volume functions for different edges) we show how to compute the minimum cost in the infinite-size limit. The argument uses a probabilistic r...
