-
作者：Duer, Mirjam; Jargalsaikhan, Bolor; Still, Georg
作者单位：Universitat Trier; University of Groningen; University of Twente
摘要：This paper is concerned with so-called generic properties of general linear conic programs. Many results have been obtained on this subject during the last two decades. For example, it is known that uniqueness, strict complementarity, and nondegeneracy of optimal solutions hold for almost all problem instances. Strong duality holds generically in a stronger sense, i.e., it holds for a generic subset of problem instances. In this paper, we survey known results and present new ones. In particula...
-
作者：Yamazaki, Kazutoshi
作者单位：Kansai University
摘要：A new approach to solve the continuous-time stochastic inventory problem using the fluctuation theory of Levy processes is developed. This approach involves the recent developments of the scale function that is capable of expressing many fluctuation identities of spectrally one-sided Levy processes. For the case with a fixed cost and a general spectrally positive Levy demand process, we show the optimality of an (s,S)-policy. The optimal policy and the value function are concisely expressed vi...
-
作者：Engau, Alexander
作者单位：Children's Hospital Colorado; University of Colorado System; University of Colorado Anschutz Medical Campus; University of Colorado Denver
摘要：The mathematical equivalence between linear scalarizations in multiobjective programming and expected- value functions in stochastic optimization suggests to investigate and establish further conceptual analogies between these two areas. In this paper, we focus on the notion of proper efficiency that allows us to provide a first comprehensive analysis of solution and scenario tradeoffs in stochastic optimization. In generalization of two standard characterizations of properly efficient solutio...
-
作者：Chestnut, Stephen R.; Zenklusen, Rico
作者单位：Swiss Federal Institutes of Technology Domain; ETH Zurich
摘要：Interdiction problems ask about the worst-case impact of a limited change to an underlying optimization problem. They are a natural way to measure the robustness of a system or to identify its weakest spots. Interdiction problems have been studied for a wide variety of classical combinatorial optimization problems. Most interdiction problems are NP-hard, and furthermore, even designing efficient approximation algorithms that allow for estimating the order of magnitude of a worst-case impact ha...
-
作者：Levi, Retsef; Roundy, Robin; Van Anh Truong; Wang, Xinshang
作者单位：Massachusetts Institute of Technology (MIT); Brigham Young University; Columbia University
摘要：We develop the first algorithmic approach to compute provably good ordering policies for a multi-echelon, stochastic inventory system facing correlated, nonstationary and evolving demands over a finite horizon. Specifically, we study the serial system. Our approach is computationally efficient and provides worst-case guarantees. That is, the expected cost of the algorithms is guaranteed to be within a constant factor of the optimal expected cost; depending on the assumption the constant varies...
-
作者：Kurpisz, Adam; Leppanen, Samuli; Mastrolilli, Monaldo
作者单位：Universita della Svizzera Italiana
摘要：The Lasserre/Sum-of-Squares (SoS) hierarchy is a systematic procedure for constructing a sequence of increasingly tight semidefinite relaxations. It is known that the hierarchy converges to the 0/1 polytope in n levels and captures the convex relaxations used in the best available approximation algorithms for a wide variety of optimization problems. In this paper we characterize the set of 0/1 integer linear problems and unconstrained 0/1 polynomial optimization problems that can still have an...
-
作者：Babichenko, Yakov; Barman, Siddharth; Peretz, Ron
作者单位：Technion Israel Institute of Technology; Indian Institute of Science (IISC) - Bangalore; Bar Ilan University
摘要：We show that in any n-player, m-action normal-form game, we can obtain an approximate equilibrium by sampling any mixed-action equilibrium a small number of times. We study three types of equilibria: Nash, correlated, and coarse-correlated. For each one we obtain upper and lower bounds on the number of samples required for the empirical distribution over the sampled action profiles to form an approximate equilibrium with probability close to 1. These bounds imply that using a small number of s...
-
作者：Pang, Jong-Shi; Razaviyayn, Meisam; Alvarado, Alberth
作者单位：University of Southern California
摘要：Motivated by a class of applied problems arising from physical layer based security in a digital communication system, in particular, by a secrecy sum-rate maximization problem, this paper studies a nonsmooth, difference-of-convex (dc) minimization problem. The contributions of this paper are (i) clarify several kinds of stationary solutions and their relations; (ii) develop and establish the convergence of a novel algorithm for computing a d-stationary solution of a problem with a convex feas...
-
作者：Minardi, Stefania; Savochkin, Andrei
作者单位：Hautes Etudes Commerciales (HEC) Paris; New Economic School
摘要：In the Anscombe-Aumann setup, we provide conditions for a collection of observations to be consistent with a well-known class of smooth ambiguity preferences (Klibanoff P, Marinacci M, Mukerji S (2005) A smooth model of decision making under ambiguity. Econometrica 73(6): 1849-1892.). Each observation is assumed to take the form of an equivalence between an uncertain act and a certain outcome. We provide three results that describe these conditions for data sets of different cardinality. Our f...
-
作者：Drakopoulos, Kimon; Ozdaglar, Asuman; Tsitsiklis, John N.
作者单位：Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT)
摘要：We consider the propagation of a contagion process (epidemic) on a network and study the problem of dynamically allocating a fixed curing budget to the nodes of the graph, at each time instant. For bounded degree graphs, we provide a lower bound on the expected time to extinction under any such dynamic allocation policy, in terms of a combinatorial quantity that we call the resistance of the set of initially infected nodes, the available budget, and the number of nodes n. Specifically, we cons...
