-
作者：Subramanian, Vijay G.
作者单位：Maynooth University
摘要：We consider a single server discrete-time system with a fixed number of users where the server picks operating points from a compact, convex, and coordinate convex set. For this system, we analyse the performance of a stabilising policy that at any given time picks operating points from the allowed rate region that maximise a weighted sum of rates, where the weights depend on the work loads of the users. Assuming a large deviations principle (LDP) for the arrival processes in the Skorohod spac...
-
作者：Jelenkovic, Predrag R.; Tan, Jian
作者单位：Columbia University; International Business Machines (IBM); IBM USA
摘要：Power law distributions have been repeatedly observed in a wide variety of socioeconomic, biological, and technological areas. In many of the observations, e. g., city populations and sizes of living organisms, the objects of interest evolve because of the replication of their many independent components, e. g., births and deaths of individuals and replications of cells. Furthermore, the rates of replications are often controlled by exogenous parameters causing periods of expansion and contrac...
-
作者：Bertsimas, Dimitris; Doan, Xuan Vinh; Natarajan, Karthik; Teo, Chung-Piaw
作者单位：Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT); City University of Hong Kong; National University of Singapore
摘要：We propose a semidefinite optimization (SDP) model for the class of minimax two-stage stochastic linear optimization problems with risk aversion. The distribution of second-stage random variables belongs to a set of multivariate distributions with known first and second moments. For the minimax stochastic problem with random objective, we provide a tight SDP formulation. The problem with random right-hand side is NP-hard in general. In a special case, the problem can be solved in polynomial ti...
-
作者：Conforti, Michele; Wolsey, Laurence A.; Zambelli, Giacomo
作者单位：University of Padua; Universite Catholique Louvain
摘要：We consider the mixed-integer version of bipartite vertex cover. This is equivalent to a mixed-integer network dual model, introduced recently, that generalizes several mixed-integer sets arising in production planning. We derive properties of inequalities that are valid for the convex hull of the mixed-integer bipartite covers by projecting an extended formulation onto the space of the original variables. This permits us to give a complete description of the facet-inducing inequalities of the...
-
作者：Cook, William J.; Espinoza, Daniel G.; Goycoolea, Marcos
作者单位：University System of Georgia; Georgia Institute of Technology; Universidad de Chile; Universidad Adolfo Ibanez
摘要：We extend the work of Letchford [Letchford, A. N. 2000. Separating a superclass of comb inequalities in planar graphs. Math. Oper. Res. 25 443-454] by introducing a new class of valid inequalities for the traveling salesman problem, called the generalized domino-parity (GDP) constraints. Just as Letchford's domino-parity constraints generalize comb inequalities, GDP constraints generalize the most well-known multiple-handle constraints, including clique-tree, bipartition, path, and star inequa...
-
作者：Dieker, A. B.; Warren, J.
作者单位：University System of Georgia; Georgia Institute of Technology; University of Warwick
摘要：This paper studies the queue-length process in series Jackson networks with external input to the first station only. We show that its Markov transition probabilities can be written as a finite sum of noncrossing probabilities, so that questions on time-dependent queueing behavior are translated to questions on noncrossing probabilities. This makes previous work on noncrossing probabilities relevant to queueing systems and allows new queueing results to be established. To illustrate the latter...
-
作者：Lee, Jon; Sviridenko, Maxim; Vondrak, Jan
作者单位：International Business Machines (IBM); IBM USA; International Business Machines (IBM); IBM USA
摘要：Submodular function maximization is a central problem in combinatorial optimization, generalizing many important NP-hard problems including max cut in digraphs, graphs, and hypergraphs; certain constraint satisfaction problems; maximum entropy sampling; and maximum facility location problems. Our main result is that for any k >= 2 and any epsilon > 0, there is a natural local search algorithm that has approximation guarantee of 1/(k+epsilon) for the problem of maximizing a monotone submodular ...
-
作者：Zheng, Xiaojin; Sun, Xiaoling; Li, Duan; Xia, Yong
作者单位：Fudan University; Chinese University of Hong Kong; Beihang University
摘要：We investigate in this paper the Lagrangian duality properties of linear equality constrained binary quadratic programming. We derive an underestimation of the duality gap between the primal problem and its Lagrangian dual or SDP relaxation, using the distance from the set of binary integer points to certain affine subspace, while the computation of this distance can be achieved by the cell enumeration of hyperplane arrangement. Alternative Lagrangian dual schemes via the exact penalty and the...
-
作者：Bertsimas, Dimitris; Iancu, Dan A.; Parrilo, Pablo A.
作者单位：Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT)
摘要：In this paper, we prove the optimality of disturbance-affine control policies in the context of one-dimensional, constrained, multistage robust optimization. Our results cover the finite-horizon case, with minimax (worst-case) objective, and convex state costs plus linear control costs. We develop a new proof methodology, which explores the relationship between the geometrical properties of the feasible set of solutions and the structure of the objective function. Apart from providing an elega...
-
作者：Basu, Amitabh; Conforti, Michele; Cornuejols, Gerard; Zambelli, Giacomo
作者单位：Carnegie Mellon University; University of Padua
摘要：We consider a model that arises in integer programming and show that all irredundant inequalities are obtained from maximal lattice-free convex sets in an affine subspace. We also show that these sets are polyhedra. The latter result extends a theorem of Lovasz characterizing maximal lattice-free convex sets in R-n.
