-
作者：Gupta, Anupam; Lee, Euiwoong; Li, Jason; Mucha, Marcin; Newman, Heather; Sarkar, Sherry
作者单位：Carnegie Mellon University; University of Michigan System; University of Michigan; University of California System; University of California Berkeley; University of Warsaw
摘要：We show how to round any half-integral solution to the subtour-elimination relaxation for the TSP, while losing a less-than-\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$-$$\end{document} 1.5 factor. Such a rounding algorithm was recently given by Karlin, Klein, and Oveis Gharan based on sampling from max-entropy...
-
作者：Pass, Brendan; Vargas-Jimenez, Adolfo
作者单位：University of Alberta; University of Ottawa
摘要：We establish a general condition on the cost function to obtain uniqueness and Monge solutions in the multi-marginal optimal transport problem, under the assumption that a given collection of the marginals are absolutely continuous with respect to local coordinates. When only the first marginal is assumed to be absolutely continuous, our condition is equivalent to the twist on splitting sets condition found in Kim and Pass (SIAM J Math Anal 46:1538-1550, 2014; SIAM J Math Anal 46:1538-1550, 20...
-
作者：Cohen-Addad, Vincent; Moemke, Tobias; Verdugo, Victor
作者单位：Alphabet Inc.; Google Incorporated; University of Augsburg; Universidad de O'Higgins
摘要：In the non-uniform sparsest cut problem, we are given a supply graph G and a demand graph D, both with the same set of nodes V. The goal is to find a cut of V that minimizes the ratio of the total capacity on the edges of G crossing the cut over the total demand of the crossing edges of D. In this work, we study the non-uniform sparsest cut problem for supply graphs with bounded treewidth k. For this case, Gupta et al. (ACM STOC, 2013) obtained a 2-approximation with polynomial running time fo...
-
作者：Comaneci, Andrei; Joswig, Michael
作者单位：Technical University of Berlin; Max Planck Society
摘要：Fermat-Weber points with respect to an asymmetric tropical distance function are studied. It turns out that they correspond to the optimal solutions of a transportation problem. The results are applied to obtain a new method for computing consensus trees in phylogenetics. This method has several desirable properties; e.g., it is Pareto and co-Pareto on rooted triplets.
-
作者：Curtis, Frank E.; O'Neill, Michael J.; Robinson, Daniel P.
作者单位：Lehigh University; University of North Carolina; University of North Carolina Chapel Hill
摘要：A worst-case complexity bound is proved for a sequential quadratic optimization (commonly known as SQP) algorithm that has been designed for solving optimization problems involving a stochastic objective function and deterministic nonlinear equality constraints. Barring additional terms that arise due to the adaptivity of the monotonically nonincreasing merit parameter sequence, the proved complexity bound is comparable to that known for the stochastic gradient algorithm for unconstrained nonc...
-
作者：Baldwin, Elizabeth; Bichler, Martin; Fichtl, Maximilian; Klemperer, Paul
作者单位：University of Oxford; University of Oxford; Technical University of Munich; University of Oxford; University of Oxford
摘要：We show the strong substitutes product-mix auction bidding language provides an intuitive and geometric interpretation of strong substitutes as Minkowski differences between sets that are easy to identify. We prove that competitive equilibrium prices for agents with strong substitutes preferences can be computed by minimizing the difference between two linear programs for the positive and the negative bids with suitably relaxed resource constraints. This also leads to a new algorithm for compu...
-
作者：Harks, Tobias; Schedel, Anja
作者单位：University of Augsburg
摘要：We study a Stackelberg game with multiple leaders and a continuum of followers that are coupled via congestion effects. The followers' problem constitutes a nonatomic congestion game, where a population of infinitesimal players is given and each player chooses a resource. Each resource has a linear cost function which depends on the congestion of this resource. The leaders of the Stackelberg game each control a resource and determine a price per unit as well as a service capacity for the resou...
-
作者：Borst, Sander; Dadush, Daniel; Huiberts, Sophie; Kashaev, Danish
作者单位：Centrum Wiskunde & Informatica (CWI); Utrecht University; Columbia University
摘要：Explorable heap selection is the problem of selecting the nth smallest value in a binary heap. The key values can only be accessed by traversing through the underlying infinite binary tree, and the complexity of the algorithm is measured by the total distance traveled in the tree (each edge has unit cost). This problem was originally proposed as a model to study search strategies for the branch-and-bound algorithm with storage restrictions by Karp, Saks and Widgerson (FOCS '86), who gave deter...
-
作者：Bestuzheva, Ksenia; Gleixner, Ambros; Achterberg, Tobias
作者单位：Zuse Institute Berlin
摘要：The reformulation-linearization technique (RLT) is a prominent approach to constructing tight linear relaxations of non-convex continuous and mixed-integer optimization problems. The goal of this paper is to extend the applicability and improve the performance of RLT for bilinear product relations. First, we present a method for detecting bilinear product relations implicitly contained in mixed-integer linear programs, which is based on analyzing linear constraints with binary variables, thus ...
-
作者：Dadush, Daniel; Koh, Zhuan Khye; Natura, Bento; Vegh, Laszlo A.
作者单位：University System of Georgia; Georgia Institute of Technology; University of London; London School Economics & Political Science
摘要：We study the circuit diameter of polyhedra, introduced by Borgwardt, Finhold, and Hemmecke (SIAM J. Discrete Math. 29(1), 113-121 (2015)) as a relaxation of the combinatorial diameter. We show that the circuit diameter of a system {x is an element of Rn:Ax=b,0 <= x <= u}\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document...
