-
作者：Grandoni, Fabrizio; Rothvoss, Thomas; Sanita, Laura
作者单位：University of Rome Tor Vergata; Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne
摘要：The virtual private network problem (VPN) models scenarios in which traffic is uncertain or rapidly changing. The goal is supporting at minimum cost a given family of traffic matrices, which are implicitly given by upper bounds on the ingoing and outgoing traffic at each node. Costs are classically defined by a linear function (linear VPN), but we consider here also the more general case of concave increasing costs (concave VPN). In this paper we give the first constant factor approximation fo...
-
作者：Jansen, Klaus; Solis-Oba, Roberto
作者单位：University of Kiel; Western University (University of Western Ontario)
摘要：In the cutting stock problem, we are given a set of objects of different types, and the goal is to pack them all in the minimum possible number of identical bins. All objects have integer lengths, and objects of different types have different sizes. The total length of the objects packed in a bin cannot exceed the capacity of the bin. In this paper, we consider the version of the problem in which the number of different object types is constant, and we present a polynomial-time algorithm that ...
-
作者：Fleischer, Lisa; Goemans, Michel X.; Mirrokni, Vahab S.; Sviridenko, Maxim
作者单位：Dartmouth College; Massachusetts Institute of Technology (MIT); Alphabet Inc.; Google Incorporated; International Business Machines (IBM); IBM USA
摘要：A separable assignment problem (S A P) is defined by a set of bins and a set of items to pack in each bin; a value, f(ij), for assigning item j to bin i; and a separate packing constraint for each bin-i.e., for each bin, a family of subsets of items that fit in to that bin. The goal is to pack items into bins to maximize the aggregate value. This class of problems includes the maximum generalized assignment problem (G A P)(1) and a distributed caching problem (DCP) described in this paper. Giv...
-
作者：Ralph, Daniel; Xu, Huifu
作者单位：University of Cambridge; University of Southampton
摘要：This paper presents an asymptotic analysis of a Monte Carlo method, variously known as sample average approximation (SAA) or sample path optimization (SPO), for a general two-stage stochastic minimization problem. We study the case when the second-stage problem may have multiple local optima or stationary points that are not global solutions and SAA is implemented using a general nonlinear programming solver that is only guaranteed to find stationary points. New optimality conditions are devel...
-
作者：Lon, Pui Chan; Zervos, Mihail
作者单位：University of London; London School Economics & Political Science
摘要：We formulate and solve a problem that combines the features of the so-called monotone follower of singular stochastic control theory with optimal stopping. In particular, we consider a stochastic system whose uncontrolled state dynamics are modelled by a general one-dimensional Ito diffusion. The aim of the problem that we solve is to maximise the utility derived from the system's state at the discretionary time when the system's control is terminated. This objective is reflected by the perfor...
-
作者：Ambuehl, Christoph; Mastrolilli, Monaldo; Mutsanas, Nikolaus; Svensson, Ola
作者单位：University of Liverpool; Universita della Svizzera Italiana; Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne
摘要：We consider the single-machine scheduling problem to minimize the weighted sum of completion times under precedence constraints. In a series of recent papers, it was established that this scheduling problem is a special case of minimum weighted vertex cover. In this paper, we show that the vertex cover graph associated with the scheduling problem is exactly the graph of incomparable pairs defined in the dimension theory of partial orders. Exploiting this relationship allows us to present a fra...
-
作者：Bertsimas, Dimitris; Goyal, Vineet; Sun, Xu Andy
作者单位：Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT); Columbia University
摘要：In this paper, we show a significant role that geometric properties of uncertainty sets, such as symmetry, play in determining the power of robust and finitely adaptable solutions in multistage stochastic and adaptive optimization problems. We consider a fairly general class of multistage mixed integer stochastic and adaptive optimization problems and propose a good approximate solution policy with performance guarantees that depend on the geometric properties of the uncertainty sets. In parti...
-
作者：Cavazos-Cadena, Rolando; Hernandez-Hernandez, Daniel
作者单位：CIMAT - Centro de Investigacion en Matematicas
摘要：This work concerns Markov decision processes with finite state space and compact action set. The performance of a control policy is measured by a risk-sensitive average cost criterion and, under standard continuity-compactness conditions, it is shown that the discounted approximations converge to the optimal value function, and that the superior and inferior limit average criteria have the same optimal value function. These conclusions are obtained for every nonnull risk-sensitivity coefficien...
-
作者：Averkov, Gennadiy; Wagner, Christian; Weismantel, Robert
作者单位：Otto von Guericke University; Swiss Federal Institutes of Technology Domain; ETH Zurich
摘要：A convex set with nonempty interior is maximal lattice-free if it is inclusion maximal with respect to the property of not containing integer points in its interior. Maximal lattice-free convex sets are known to be polyhedra. The precision of a rational polyhedron P in R-d is the smallest natural number s such that sP is an integral polyhedron. In this paper we show that, up to affine mappings preserving Z(d), the number of maximal lattice-free rational polyhedra of a given precision s is fini...
-
作者：Candogan, Ozan; Menache, Ishai; Ozdaglar, Asuman; Parrilo, Pablo A.
作者单位：Massachusetts Institute of Technology (MIT); Microsoft
摘要：In this paper we introduce a novel flow representation for finite games in strategic form. This representation allows us to develop a canonical direct sum decomposition of an arbitrary game into three components, which we refer to as the potential, harmonic, and nonstrategic components. We analyze natural classes of games that are induced by this decomposition, and in particular, focus on games with no harmonic component and games with no potential component. We show that the first class corre...
