1-2期

最新文章

• 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...
• 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...
• 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...
• Intrinsic volumes of symmetric cones and applications in convex programming AI翻译
  作者：Amelunxen, Dennis; Buergisser, Peter
  作者单位：University of Manchester; Technical University of Berlin
  摘要：We express the probability distribution of the solution of a random (standard Gaussian) instance of a convex cone program in terms of the intrinsic volumes and curvature measures of the reference cone. We then compute the intrinsic volumes of the cone of positive semidefinite matrices over the real numbers, over the complex numbers, and over the quaternions in terms of integrals related to Mehta's integral. In particular, we obtain a closed formula for the probability that the solution of a ra...
• Improved approximation algorithms for two variants of the stable marriage problem with ties AI翻译
  作者：Huang, Chien-Chung; Kavitha, Telikepalli
  作者单位：Chalmers University of Technology; Tata Institute of Fundamental Research (TIFR)
  摘要：We consider the problem of computing a large stable matching in a bipartite graph where each vertex ranks its neighbors in an order of preference, perhaps involving ties. Let the matched partner of u in a matching M be M(u). A matching M is said to be stable if there is no edge (a, b) such that a is unmatched or prefers b to M(a) and similarly, b is unmatched or prefers a to M(b). While a stable matching in G can be easily computed in linear time by the Gale-Shapley algorithm, it is known that...
• Sufficiency of cut-generating functions AI翻译
  作者：Cornuejols, Gerard; Wolsey, Laurence; Yildiz, Sercan
  作者单位：Carnegie Mellon University; Universite Catholique Louvain
  摘要：The concept of cut-generating function has its origin in the work of Gomory and Johnson from the 1970s. It has received renewed attention in the past few years. Recently Conforti, Cornu,jols, Daniilidis, Lemar,chal, and Malick proposed a general framework for studying cut-generating functions. However, they gave an example showing that not all cuts can be produced by cut-generating functions in this framework. They conjectured a natural condition under which cut-generating functions might be s...
• Attraction of Newton method to critical Lagrange multipliers: fully quadratic case AI翻译
  作者：Izmailov, A. F.; Uskov, E. I.
  作者单位：Lomonosov Moscow State University
  摘要：In this paper we continue the studies of the persistent effect of attraction of Newton-type iterations for optimality systems to critical Lagrange multipliers. It appears very important to understand the nature of this striking phenomenon, in particular, because it is precisely the reason of slow convergence of such methods when applied to problems with degenerate constraints. All previously known results concerned with this effect were a posteriori by nature: they were showing that in case of...