1期

最新文章

• Sum-of-squares chordal decomposition of polynomial matrix inequalities AI翻译
  作者：Zheng, Yang; Fantuzzi, Giovanni
  作者单位：University of California System; University of California San Diego; Imperial College London
  摘要：We prove decomposition theorems for sparse positive (semi)definite polynomialmatrices that can be viewed as sparsity-exploiting versions of the Hilbert-Artin, Reznick, Putinar, and Putinar-Vasilescu Positivstellensatze. First, we establish that a polynomial matrix P( x) with chordal sparsity is positive semidefinite for all x is an element of R-n if and only if there exists a sum-of-squares (SOS) polynomial sigma( x) such that s P is a sum of sparse SOS matrices. Second, we show that setting s...
• The smoothed number of Pareto-optimal solutions in bicriteria integer optimization AI翻译
  作者：Beier, Rene; Roeglin, Heiko; Roesner, Clemens; Voecking, Berthold
  作者单位：Max Planck Society; University of Bonn; RWTH Aachen University
  摘要：A well-established heuristic approach for solving bicriteria optimization problems is to enumerate the set of Pareto-optimal solutions. The heuristics following this principle are often successful in practice. Their running time, however, depends on the number of enumerated solutions, which is exponential in the worst case. We study bicriteria integer optimization problems in the model of smoothed analysis, in which inputs are subject to a small amount of random noise, and we prove an almost t...
• The role of optimization in some recent advances in data-driven decision-making AI翻译
  作者：Baardman, Lennart; Cristian, Rares; Perakis, Georgia; Singhvi, Divya; Lami, Omar Skali; Thayaparan, Leann
  作者单位：University of Michigan System; University of Michigan; Massachusetts Institute of Technology (MIT); New York University
  摘要：Data-driven decision-making has garnered growing interest as a result of the increasing availability of data in recent years. With that growth many opportunities and challenges have sprung up in the areas of predictive and prescriptive analytics. Often, optimization can play an important role in tackling these issues. In this paper, we review some recent advances that highlight the difference that optimization can make in data-driven decision-making. We discuss some of our contributions that a...
• Lower bounds on the size of general branch-and-bound trees AI翻译
  作者：Dey, Santanu S.; Dubey, Yatharth; Molinaro, Marco
  作者单位：University System of Georgia; Georgia Institute of Technology; Pontificia Universidade Catolica do Rio de Janeiro
  摘要：A general branch-and-bound tree is a branch-and-bound tree which is allowed to use general disjunctions of the form pi(T) x <= pi(0) V pi(T) x >= pi(0) + 1, where pi is an integer vector and pi(0) is an integer scalar, to create child nodes. We construct a packing instance, a set covering instance, and a Traveling Salesman Problem instance, such that any general branch-and-bound tree that solves these instances must be of exponential size. We also verify that an exponential lower bound on the ...
• Approximation algorithms for the generalized incremental knapsack problem AI翻译
  作者：Faenza, Yuri; Segev, Danny; Zhang, Lingyi
  作者单位：Columbia University; Tel Aviv University
  摘要：We introduce and study a discrete multi-period extension of the classical knapsack problem, dubbed generalized incremental knapsack. In this setting, we are given a set of n items, each associated with a non-negative weight, and T time periods with non-decreasing capacities W-1 <= ... <= W-T. When item i is inserted at time t, we gain a profit of p(it ); however, this item remains in the knapsack for all subsequent periods. The goal is to decide if and when to insert each item, subject to the ...
• Arboricity games: the core and the nucleolus AI翻译
  作者：Xiao, Han; Fang, Qizhi
  作者单位：Ocean University of China
  摘要：The arboricity of a graph is the minimum number of forests required to cover all its edges. In this paper, we examine arboricity from a game-theoretic perspective and investigate cost-sharing in the minimum forest cover problem. We introduce the arboricity game as a cooperative cost game defined on a graph. The players are edges, and the cost of each coalition is the arboricity of the subgraph induced by the coalition. We study properties of the core and propose an efficient algorithm for comp...
• A reformulation-linearization technique for optimization over simplices AI翻译
  作者：Selvi, Aras; den Hertog, Dick; Wiesemann, Wolfram
  作者单位：Imperial College London; University of Amsterdam
  摘要：We study non-convex optimization problems over simplices. We show that for a large class of objective functions, the convex approximation obtained from the Reformulation-Linearization Technique (RLT) admits optimal solutions that exhibit a sparsity pattern. This characteristic of the optimal solutions allows us to conclude that (i) a linear matrix inequality constraint, which is often added to tighten the relaxation, is vacuously satisfied and can thus be omitted, and (ii) the number of decisi...
• Error bounds, facial residual functions and applications to the exponential cone AI翻译
  作者：Lindstrom, Scott B.; Lourenco, Bruno F.; Pong, Ting Kei
  作者单位：Curtin University; Research Organization of Information & Systems (ROIS); Institute of Statistical Mathematics (ISM) - Japan; Hong Kong Polytechnic University
  摘要：We construct a general framework for deriving error bounds for conic feasibility problems. In particular, our approach allows one to work with cones that fail to be amenable or even to have computable projections, two previously challenging barriers. For the purpose, we first show how error bounds may be constructed using objects called one-step facial residual functions. Then, we develop several tools to compute these facial residual functions even in the absence of closed form expressions fo...
• Non-asymptotic superlinear convergence of standard quasi-Newton methods AI翻译
  作者：Jin, Qiujiang; Mokhtari, Aryan
  作者单位：University of Texas System; University of Texas Austin
  摘要：In this paper, we study and prove the non-asymptotic superlinear convergence rate of the Broyden class of quasi-Newton algorithms which includes the Davidon-Fletcher-Powell (DFP) method and the Broyden-Fletcher-Goldfarb-Shanno (BFGS) method. The asymptotic superlinear convergence rate of these quasi-Newton methods has been extensively studied in the literature, but their explicit finite-time local convergence rate is not fully investigated. In this paper, we provide a finite-time (non-asymptot...
• Towards improving Christofides algorithm on fundamental classes by gluing convex combinations of tours AI翻译
  作者：Haddadan, Arash; Newman, Alantha
  作者单位：Carnegie Mellon University; Centre National de la Recherche Scientifique (CNRS); Communaute Universite Grenoble Alpes; Universite Grenoble Alpes (UGA)
  摘要：We present a new approach for gluing tours over certain tight, 3-edge cuts. Gluing over 3-edge cuts has been used in algorithms for finding Hamilton cycles in special graph classes and in proving bounds for 2-edge-connected subgraph problem, but not much was known in this direction for gluing connected multigraphs. We apply this approach to the traveling salesman problem (TSP) in the case when the objective function of the subtour elimination relaxation is minimized by a theta-cyclic point: x(...