-
作者：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...
-
作者：Diakonikolas, Jelena; Guzman, Cristobal
作者单位：University of Wisconsin System; University of Wisconsin Madison; Pontificia Universidad Catolica de Chile; Pontificia Universidad Catolica de Chile
摘要：Composite minimization is a powerful framework in large-scale convex optimization, based on decoupling of the objective function into terms with structurally different properties and allowing for more flexible algorithmic design. We introduce a new algorithmic framework for complementary composite minimization, where the objective function decouples into a (weakly) smooth and a uniformly convex term. This particular form of decoupling is pervasive in statistics and machine learning, due to its...
-
作者：Zadik, Ilias; Lubin, Miles; Vielma, Juan Pablo
作者单位：Massachusetts Institute of Technology (MIT)
摘要：Mixed-integer convex representable (MICP-R) sets are those sets that can be represented exactly through a mixed-integer convex programming formulation. Following up on recent work by Lubin et al. (in: Eisenbrand (ed) Integer Programming and Combinatorial Optimization - 19th International Conference, Springer, Waterloo), (Math. Oper. Res. 47:720-749, 2022) we investigate structural geometric properties of MICP-R sets, which strongly differentiate them from the class of mixed-integer linear repr...
