-
作者：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...
-
作者：Buchbinder, Niv; Feldman, Moran; Schwartz, Roy
作者单位：Tel Aviv University; Open University Israel; Technion Israel Institute of Technology
摘要：Fast algorithms for submodular maximization problems have a vast potential use in applicative settings, such as machine learning, social networks, and economics. Though fast algorithms were known for some special cases, only recently such algorithms were considered in the general case of maximizing a monotone submodular function subject to a matroid independence constraint. The known fast algorithm matches the best possible approximation guarantee, while trying to reduce the number of value or...
-
作者：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...
-
作者：Atar, Rami; Saha, Subhamay
作者单位：Technion Israel Institute of Technology; Indian Institute of Technology System (IIT System); Indian Institute of Technology (IIT) - Guwahati
摘要：A multiclass queue with many servers is considered, where customers make a join-or-leave decision upon arrival based on queue length information, without knowing the state of other queues. A game theoretic formulation is proposed and analyzed, that takes advantage of a phenomenon unique to heavy traffic regimes, namely, Reiman's snaphshot principle, by which waiting times are predicted with high precision by the information available upon arrival. The payoff considered is given as a random var...
-
作者：Ramaswamy, Arunselvan; Bhatnagar, Shalabh
作者单位：Indian Institute of Science (IISC) - Bangalore
摘要：In this paper, the stability theorem of Borkar and Meyn is extended to include the case when the mean field is a set-valued map. Two different sets of sufficient conditions are presented that guarantee the stability and convergence of stochastic recursive inclusions. Our work builds on the works of Benaim, Hofbauer and Sorin as well as Borkar and Meyn. As a corollary to one of the main theorems, a natural generalization of the Borkar and Meyn theorem follows. In addition, the original theorem ...
-
作者：Bo, Lijun; Capponi, Agostino
作者单位：Chinese Academy of Sciences; University of Science & Technology of China, CAS; Chinese Academy of Sciences; Columbia University
摘要：We consider the portfolio decision problem of a risky investor. The investor borrows at a rate higher than his lending rate and invests in a risky bond whose market price is correlated with the credit quality of the investor. By viewing the concave drift of the wealth process as a continuous function of the admissible control, we characterize the optimal strategy in terms of a relation between a critical borrowing threshold and solutions of a system of first-order conditions. We analyze the no...
-
作者：Kolokoltsov, Vassili
作者单位：University of Warwick
摘要：In this paper we extend the framework of the evolutionary inspection game put forward recently by the author and coworkers to a large class of conflict interactions to address the pressure executed by the major player (or principal) on the large group of small players who can resist this pressure or collaborate with the major player. We prove rigorous results on the convergence of various Markov decision models of interacting small agents (including evolutionary growth), i.e., pairwise, in gro...
-
作者：Huang, Chien-Chung; Kavitha, Telikepalli
作者单位：Chalmers University of Technology; Tata Institute of Fundamental Research (TIFR)
摘要：We revisit the classical maximum weight matching problem in general graphs with nonnegative integral edge weights. We present an algorithm that operates by decomposing the problem into W unweighted versions of the problem, where W is the largest edge weight. Our algorithm has running time as good as the current fastest algorithms for the maximum weight matching problem when W is small. One of the highlights of our algorithm is that it also produces an integral optimal dual solution; thus our a...
-
作者：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...
-
作者：Amarante, Massimiliano
作者单位：Universite de Montreal; Universite de Montreal
摘要：The concept of ambiguity designates those situations where the information available to the decision maker is insufficient to form a probabilistic view of the world. Thus, it has provided the motivation for departing from the subjective expected utility (SEU) paradigm. Yet, the formalization of the concept is missing. This is a grave omission as it leaves nonexpected utility models hanging on shaky ground. In particular, it leaves unanswered basic questions such as the following: (1) Does ambi...
