-
作者：Wang, Mengdi
作者单位：Princeton University
摘要：We propose a novel randomized linear programming algorithm for approximating the optimal policy of the discounted-reward and average-reward Markov decision problems. By leveraging the value-policy duality, the algorithm adaptively samples state-action-state transitions and makes exponentiated primal-dual updates. We show that it finds an f-optimal policy using nearly linear runtime in the worst case for a fixed value of the discount factor. When the Markov decision process is ergodic and speci...
-
作者：Solan, Eilon; Solan, Omri N.
作者单位：Tel Aviv University
摘要：We prove that every multiplayer quitting game admits a sunspot epsilon-equilibrium for every epsilon> 0, that is, an e-equilibrium in an extended game in which the players observe a public signal at every stage. We also prove that, if a certain matrix that is derived from the payoffs in the game is not a Q-matrix in the sense of linear complementarity problems, then the game admits a uniform epsilon-equilibrium for every epsilon > 0.
-
作者：Bot, Radu Ioan; Dang-Khoa Nguyen
作者单位：University of Vienna; Babes Bolyai University from Cluj
摘要：We propose two numerical algorithms in the fully nonconvex setting for the minimization of the sum of a smooth function and the composition of a nonsmooth function with a linear operator. The iterative schemes are formulated in the spirit of the proximal alternating direction method of multipliers and its linearized variant, respectively. The proximal terms are introduced via variable metrics, a fact that allows us to derive new proximal splitting algorithms for nonconvex structured optimizati...
-
作者：Eshragh, Ali; Filar, Jerzy A.; Kalinowski, Thomas; Mohammadian, Sogol
作者单位：University of Newcastle; University of Queensland; University of New England
摘要：We study a certain polytope arising from embedding the Hamiltonian cycle problem in a discounted Markov decision process. The Hamiltonian cycle problem can be reduced to finding particular extreme points of a certain polytope associated with the input graph. This polytope is a subset of the space of discounted occupational measures. We characterize the feasible bases of the polytope for a general input graph G and determine the expected numbers of different types of feasible bases when the und...
-
作者：Kapoor, Sanjiv; Shin, Junghwan
作者单位：Illinois Institute of Technology
摘要：We address the performance of selfish network routing in multicommodity flows where the latency or delay function on edges is dependent on the flow of individual commodities, rather than on the aggregate flow. An application of this study is the analysis of a network with differentiated traffic, that is, in transportation networks where there are multiple types of traffic and in networks where traffic is prioritized according to type classification. We consider the inefficiency of equilibrium ...
-
作者：Hirai, Hiroshi; Oshiro, Ryunosuke; Tanaka, Ken'ichiro
作者单位：University of Tokyo
摘要：In this paper, we address the problem of counting integer points in a rational polytope described by P(y) = {x is an element of R-m: Ax = y, x >= 0}, where A is an n x in integer matrix and y is an n-dimensional integer vector. We study the Z transformation approach initiated in works by Brion and Vergne, Beck, and Lasserre and Zeron from the numerical analysis point of view and obtain a new algorithm on this problem. If A is nonnegative, then the number of integer points in P(y) can be comput...
-
作者：Paul, Alice; Freund, Daniel; Ferber, Aaron; Shmoys, David B.; Williamson, David P.
作者单位：Brown University; Massachusetts Institute of Technology (MIT); Cornell University
摘要：We consider constrained versions of the prize-collecting traveling salesman and the prize-collecting minimum spanning tree problems. The goal is to maximize the number of vertices in the returned tour/tree subject to a bound on the tour/tree cost. Rooted variants of the problems have the additional constraint that a given vertex, the root, must be contained in the tour/tree. We present a 2-approximation algorithm for the rooted and unrooted versions of both the tree and tour variants. The algo...
-
作者：Huang, Yonghui; Guo, Xianping
作者单位：Sun Yat Sen University
摘要：This paper studies a multiconstrained problem for piecewise deterministic Markov decision processes (PDMDPs) with unbounded cost and transition rates. The goal is to minimize one type of expected finite-horizon cost over history-dependent policies while keeping some other types of expected finite-horizon costs lower than some tolerable bounds. Using the Dynkin formula for the PDMDPs, we obtain an equivalent characterization of occupancy measures and express the expected finite-horizon costs in...
-
作者：Gupta, Varun; Moseley, Benjamin; Uetz, Marc; Xie, Qiaomin
作者单位：University of Chicago; Carnegie Mellon University; University of Twente; Massachusetts Institute of Technology (MIT)
摘要：This paper establishes performance guarantees for online algorithms that schedule stochastic, nonpreemptive jobs on unrelated machines to minimize the expected total weighted completion time. Prior work on unrelated machine scheduling with stochastic jobs was restricted to the offline case and required linear or convex programming relaxations for the assignment of jobs to machines. The algorithms introduced in this paper are purely combinatorial. The performance bounds are of the same order of...
-
作者：Blanchet, Jose; Chen, Xinyun
作者单位：Stanford University; The Chinese University of Hong Kong, Shenzhen
摘要：We provide the first rate of convergence to stationarity analysis for reflected Brownian motion (RBM) as the dimension grows under some uniformity conditions. In particular, if the underlying routing matrix is uniformly contractive, uniform stability of the drift vector holds, and the variances of the underlying Brownian motion (BM) are bounded, then we show that the RBM converges exponentially fast to stationarity with a relaxation time of order O(d(4)(log(d))(3)) as the dimension d -> infini...
