2015

最新文章

• Centrality of trees for capacitated -center AI翻译
  作者：An, Hyung-Chan; Bhaskara, Aditya; Chekuri, Chandra; Gupta, Shalmoli; Madan, Vivek; Svensson, Ola
  作者单位：Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne; Alphabet Inc.; Google Incorporated; University of Illinois System; University of Illinois Urbana-Champaign
  摘要：We consider the capacitated -center problem. In this problem we are given a finite set of locations in a metric space and each location has an associated non-negative integer capacity. The goal is to choose (open) locations (called centers) and assign each location to an open center to minimize the maximum, over all locations, of the distance of the location to its assigned center. The number of locations assigned to a center cannot exceed the center's capacity. The uncapacitated -center probl...
• Simple extensions of polytopes AI翻译
  作者：Kaibel, Volker; Walter, Matthias
  作者单位：Otto von Guericke University
  摘要：We introduce the simple extension complexity of a polytope as the smallest number of facets of any simple (i.e., non-degenerate in the sense of linear programming) polytope which can be projected onto . We devise a combinatorial method to establish lower bounds on the simple extension complexity and show for several polytopes that they have large simple extension complexities. These examples include both the spanning tree and the perfect matching polytopes of complete graphs, uncapacitated flo...
• Coupled and k-sided placements: generalizing generalized assignment AI翻译
  作者：Korupolu, Madhukar; Meyerson, Adam; Rajaraman, Rajmohan; Tagiku, Brian
  作者单位：Alphabet Inc.; Google Incorporated; Northeastern University
  摘要：In modern data centers and cloud computing systems, jobs often require resources distributed across nodes providing a wide variety of services. Motivated by this, we study the Coupled Placement problem, in which we place jobs into computation and storage nodes with capacity constraints, so as to optimize some costs or profits associated with the placement. The coupled placement problem is a natural generalization of the widely-studied generalized assignment problem, which concerns the placemen...
• Stable sets and graphs with no even holes AI翻译
  作者：Conforti, Michele; Gerards, Bert; Pashkovich, Kanstantsin
  作者单位：University of Padua; University of Waterloo
  摘要：We develop decomposition/composition tools for efficiently solving maximum weight stable sets problems as well as for describing them as polynomially sized linear programs (using compact systems). Some of these are well-known but need some extra work to yield polynomial decomposition schemes. We apply the tools to graphs with no even hole and no cap. A hole is a chordless cycle of length greater than three and a cap is a hole together with an additional node that is adjacent to two adjacent no...
• Uncapacitated flow-based extended formulations AI翻译
  作者：Fiorini, Samuel; Pashkovich, Kanstantsin
  作者单位：Universite Libre de Bruxelles; University of Padua
  摘要：An extended formulation of a polytope is a linear description of this polytope using extra variables besides the variables in which the polytope is defined. The interest of extended formulations is due to the fact that many interesting polytopes have extended formulations with a lot fewer inequalities than any linear description in the original space. This motivates the development of methods for, on the one hand, constructing extended formulations and, on the other hand, proving lower bounds ...
• Generalized decision rule approximations for stochastic programming via liftings AI翻译
  作者：Georghiou, Angelos; Wiesemann, Wolfram; Kuhn, Daniel
  作者单位：Massachusetts Institute of Technology (MIT); Imperial College London; Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne
  摘要：Stochastic programming provides a versatile framework for decision-making under uncertainty, but the resulting optimization problems can be computationally demanding. It has recently been shown that primal and dual linear decision rule approximations can yield tractable upper and lower bounds on the optimal value of a stochastic program. Unfortunately, linear decision rules often provide crude approximations that result in loose bounds. To address this problem, we propose a lifting technique t...
• A new warmstarting strategy for the primal-dual column generation method AI翻译
  作者：Gondzio, Jacek; Gonzalez-Brevis, Pablo
  作者单位：University of Edinburgh; Heriot Watt University; Universidad del Desarrollo
  摘要：This paper presents a new warmstarting technique in the context of a primal-dual column generation method applied to solve a particular class of combinatorial optimization problems. The technique relies on calculating an initial point and on solving auxiliary linear optimization problems to determine the step direction needed to fully restore primal and dual feasibilities after new columns arrive. Conditions on the maximum size of the cuts and on a suitable initial point are discussed. Additio...
• Solving second-order conic systems with variable precision AI翻译
  作者：Cucker, Felipe; Pena, Javier; Roshchina, Vera
  作者单位：City University of Hong Kong; Carnegie Mellon University; Federation University Australia
  摘要：We describe and analyze an interior-point method to decide feasibility problems of second-order conic systems. A main feature of our algorithm is that arithmetic operations are performed with finite precision. Bounds for both the number of arithmetic operations and the finest precision required are exhibited.
• A distributionally robust perspective on uncertainty quantification and chance constrained programming AI翻译
  作者：Hanasusanto, Grani A.; Roitch, Vladimir; Kuhn, Daniel; Wiesemann, Wolfram
  作者单位：Imperial College London; Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne; Imperial College London
  摘要：The objective of uncertainty quantification is to certify that a given physical, engineering or economic system satisfies multiple safety conditions with high probability. A more ambitious goal is to actively influence the system so as to guarantee and maintain its safety, a scenario which can be modeled through a chance constrained program. In this paper we assume that the parameters of the system are governed by an ambiguous distribution that is only known to belong to an ambiguity set chara...
• On the adaptivity gap of stochastic orienteering AI翻译
  作者：Bansal, Nikhil; Nagarajan, Viswanath
  作者单位：Eindhoven University of Technology; University of Michigan System; University of Michigan
  摘要：The input to the stochastic orienteering problem (Gupta et al. in SODA, pp 1522-1538, 2012) consists of a budget B and metric (V, d) where each vertex has a job with a deterministic reward and a random processing time (drawn from a known distribution). The processing times are independent across vertices. The goal is to obtain a non-anticipatory policy (originating from a given root vertex) to run jobs at different vertices, that maximizes expected reward, subject to the total distance travele...