-
作者：Basu, Amitabh; Martin, Kipp; Ryan, Christopher Thomas
作者单位：Johns Hopkins University; University of Chicago
摘要：Fourier-Motzkin elimination is a projection algorithm for solving finite linear programs. We extend Fourier-Motzkin elimination to semi-infinite linear programs, which are linear programs with finitely many variables and infinitely many constraints. Applying projection leads to new characterizations of important properties for primal-dual pairs of semi-infinite programs such as zero duality gap, feasibility, boundedness, and solvability. Extending the Fourier-Motzkin elimination procedure to s...
-
作者：Gensbittel, Fabien
作者单位：Universite de Toulouse; Universite Toulouse 1 Capitole
摘要：This work is devoted to extend several asymptotic results concerning repeated games with incomplete information on one side. The model we consider is a generalization of the classical model of Aumann and Maschler (Aumann et al. [Aumann RJ, Maschler M, Stearns RE (1995) Repeated Games with Incomplete Information (MIT Press, Cambridge, MA)]) to infinite action spaces and partial information. We prove an extension of the classical Cav(u) Theorem in this model for both the lower and upper value fu...
-
作者：Basu, Amitabh; Hildebrand, Robert; Koeppe, Matthias
作者单位：Johns Hopkins University; Swiss Federal Institutes of Technology Domain; ETH Zurich; University of California System; University of California Davis
摘要：We give an algorithm for testing the extremality of minimal valid functions for Gomory and Johnson's infinite group problem that are piecewise linear (possibly discontinuous) with rational breakpoints. This is the first set of necessary and sufficient conditions that can be tested algorithmically for deciding extremality in this important class of minimal valid functions. We also present an extreme function that is a piecewise linear function with some irrational breakpoints, whose extremality...
-
作者：Gupta, Anupam; Krishnaswamy, Ravishankar; Nagarajan, Viswanath; Ravi, R.
作者单位：Carnegie Mellon University; Princeton University; International Business Machines (IBM); IBM USA; Carnegie Mellon University
摘要：In the stochastic orienteering problem, we are given a finite metric space, where each node contains a job with some deterministic reward and a random processing time. The processing time distributions are known and independent across nodes. However the actual processing time of a job is not known until it is completely processed. The objective is to compute a nonanticipatory policy to visit nodes (and run the corresponding jobs) so as to maximize the total expected reward, subject to the tota...
-
作者：Chang, Cheng-Shang; Liao, Wanjiun; Lien, Ching-Min
作者单位：National Tsing Hua University; National Taiwan University
摘要：One of the fundamental problems in a cognitive radio network, known as the multichannel rendezvous problem, is for two secondary users to find a common channel that is not blocked by primary users. The basic idea for solving such a problem in most works in the literature is for the two users to select their own channel hopping sequences and then rendezvous when they both hop to a common unblocked channel at the same time. In this paper, we focus on the fundamental limits of the multichannel re...
-
作者：Kiseleva, Tatiana; Wagener, Florian
作者单位：Vrije Universiteit Amsterdam; University of Amsterdam
摘要：We study the structure of the solution set of a class of infinite-horizon dynamic programming problems with one-dimensional state spaces, as well as their bifurcations, as problem parameters are varied. The solutions are represented as the integral curves of a multivalued optimal vector field on state space. Generically, there are three types of integral curves: stable points, open intervals that are forward asymptotic to a stable point and backward asymptotic to an unstable point, and half-op...
-
作者：Mordukhovich, B. S.; Nghia, T. T. A.; Rockafellar, R. T.
作者单位：Wayne State University; King Fahd University of Petroleum & Minerals; Oakland University; University of Washington; University of Washington Seattle
摘要：The paper is devoted to full stability of optimal solutions in general settings of finite-dimensional optimization with applications to particular models of constrained optimization problems, including those of conic and specifically semidefinite programming. Developing a new technique of variational analysis and generalized differentiation, we derive second-order characterizations of full stability, in both Lipschitzian and Holderian settings, and establish their relationships with the conven...
-
作者：Shioura, Akiyoshi
作者单位：Tohoku University
摘要：We consider the maximization of a gross substitutes utility function under budget constraints. This problem naturally arises in applications such as exchange economies in mathematical economics and combinatorial auctions in (algorithmic) game theory. We show that this problem admits a polynomial-time approximation scheme (PTAS). More generally, we present a PTAS for maximizing a discrete concave function called an M-right angle-concave function under budget constraints. Our PTAS is based on ro...
-
作者：Bolte, Jerome; Gaubert, Stephane; Vigeral, Guillaume
作者单位：Universite de Toulouse; Universite Toulouse 1 Capitole; Inria; Institut Polytechnique de Paris; Ecole Polytechnique; Universite PSL; Universite Paris-Dauphine
摘要：Definable zero-sum stochastic games involve a finite number of states and action sets, and reward and transition functions, that are definable in an o-minimal structure. Prominent examples of such games are finite, semi-algebraic, or globally subanalytic stochastic games. We prove that the Shapley operator of any definable stochastic game with separable transition and reward functions is definable in the same structure. Definability in the same structure does not hold systematically: we provid...
-
作者：Girardeau, P.; Leclere, V.; Philpott, A. B.
作者单位：Institut Polytechnique de Paris; Ecole des Ponts ParisTech; University of Auckland
摘要：We prove the almost-sure convergence of a class of sampling-based nested decomposition algorithms for multistage stochastic convex programs in which the stage costs are general convex functions of the decisions and uncertainty is modelled by a scenario tree. As special cases, our results imply the almost-sure convergence of stochastic dual dynamic programming, cutting-plane and partial-sampling (CUPPS) algorithm, and dynamic outer-approximation sampling algorithms when applied to problems with...
