1-2期

最新文章

• Efficient branching rules for optimizing range and order-based objective functions AI翻译
  作者：van Rossum, Bart; Chen, Rui; Lodi, Andrea
  作者单位：Eindhoven University of Technology; The Chinese University of Hong Kong, Shenzhen
  摘要：We consider range minimization problems featuring exponentially many variables, as frequently arising in fairness-oriented or bi-objective optimization. While branch and price is successful at solving cost-oriented problems with many variables, the performance of classical branch-and-price algorithms for range minimization is drastically impaired by weak linear programming relaxations. We propose range branching, a generic branching rule that directly tackles this issue and can be used on top ...
• Logarithmic integral optimization via adaptive importance sampling based surrogation methods AI翻译
  作者：He, Ziyu; Liu, Junyi; Pang, Jong-Shi
  作者单位：University of Southern California; University of Southern California; Tsinghua University
  摘要：This paper explores Logarithmic Integral Optimization (LIO) problems, providing a unified computational framework for various tasks in computational statistics. Key among these are Maximum Likelihood Estimation (MLE) and Maximum a Posteriori (MAP) inference for probabilistic models. Specifically, we investigate scenarios where the model consists of conditional density functions with intractable normalizers. This feature can pose substantial computational challenges for the associated LIO, espe...
• The Price of Adaptivity in Stochastic Convex Optimization AI翻译
  作者：Carmon, Yair; Hinder, Oliver
  作者单位：Pennsylvania Commonwealth System of Higher Education (PCSHE); University of Pittsburgh
  摘要：We prove impossibility results for adaptivity in non-smooth stochastic convex optimization. Given a set of problem parameters we wish to adapt to, we define a price of adaptivity (PoA) that, roughly speaking, measures the multiplicative increase in suboptimality due to uncertainty in these parameters. When the initial distance to the optimum is unknown but a gradient norm bound is known, we show that the PoA is at least logarithmic for expected suboptimality, and double-logarithmic for median ...
• Sparsity and proximity transference in integer programming AI翻译
  作者：Aliev, Iskander; Celaya, Marcel; Henk, Martin
  作者单位：Cardiff University; Technical University of Berlin
  摘要：We obtain new transference bounds that connect the additive integrality gap and sparsity of solutions for integer linear programs. Specifically, we consider the integer programs min{cx:x is an element of P boolean AND Zn}\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\min \{{\varvec{c}}\cdot {\varvec{x}}: {\varvec...
• Second-order methods for quartically-regularised cubic polynomials, with applications to high-order tensor methods AI翻译
  作者：Cartis, Coralia; Zhu, Wenqi
  作者单位：University of Oxford
  摘要：There has been growing interest in high-order tensor methods for nonconvex optimization, with adaptive regularization, as they possess better/optimal worst-case evaluation complexity globally and faster convergence asymptotically. These algorithms crucially rely on repeatedly minimizing nonconvex multivariate Taylor-based polynomial sub-problems, at least locally. Finding efficient techniques for the solution of these sub-problems, beyond the second-order case, has been an open question. This ...
• A zonogon approach for computing small convex polygons of maximum perimeter AI翻译
  作者：Mulansky, Bernd; Potschka, Andreas
  作者单位：TU Clausthal
  摘要：We derive a mixed integer nonlinear programming formulation for the problem of finding a convex polygon with n vertices that is small (diameter at most one) and has maximum perimeter provided a stated conjecture is true. The formulation is based on a geometric construction using centrally symmetric polygons (zonogons). The resulting zonogons can be characterized by equivalence classes (under the action of the dihedral group) of 2n-vectors with entries either plus or minus one and a self-dualit...
• Solving nonconvex optimization problems using outer approximations of the set-copositive cone AI翻译
  作者：Gabl, Markus; Anstreicher, Kurt M.
  作者单位：Helmholtz Association; Karlsruhe Institute of Technology; University of Iowa
  摘要：We consider the solution of nonconvex quadratic optimization problems using an outer approximation of the set-copositive cone that is iteratively strengthened with cutting planes and conic constraints. Our methodology utilizes an MILP-based oracle for a generalization of the copositive cone that considers additional linear equality constraints. In numerical testing we evaluate our algorithm on a variety of different nonconvex quadratic problems.
• Weakly polynomial-time algorithms to minimize 2/3-submodular functions AI翻译
  作者：Mizutani, Ryuhei; Yoshida, Yuki
  作者单位：Keio University
  摘要：A fundamental result in combinatorial optimization is that submodular functions can be minimized in polynomial-time. In this paper, we consider the minimization problem for a more general class of set functions that contains all submodular functions. A set function is called 2/3-submodular if the submodular inequality holds for at least two pairs formed from every distinct three subsets. In this paper, we provide two weakly polynomial-time algorithms to minimize 2/3-submodular functions. We al...
• An FPTAS for Connectivity Interdiction AI翻译
  作者：Huang, Chien-Chung; Acosta, Nidia Obscura; Yingchareonthawornchai, Sorrachai
  作者单位：IMT - Institut Mines-Telecom; Institut Polytechnique de Paris; Universite PSL; Telecom SudParis; Ecole Normale Superieure (ENS); Aalto University; Swiss Federal Institutes of Technology Domain; ETH Zurich
  摘要：In the connectivity interdiction problem, we are asked to find a global graph cut and remove a subset of edges under a budget constraint, so that the total weight of the remaining edges in this cut is minimized. This problem easily includes the knapsack problem as a special case, hence it is NP-hard. For this problem, Zenklusen [Zenklusen'14] designed a polynomial-time approximation scheme (PTAS) and exact algorithms for the special case of unit edge costs. He posed the question of whether a f...
• Fully-Dynamic Load Balancing AI翻译
  作者：Foussoul, Ayoub; Goyal, Vineet; Kumar, Amit
  作者单位：Columbia University; Indian Institute of Technology System (IIT System); Indian Institute of Technology (IIT) - Delhi
  摘要：We study the classical load balancing problem in a fully dynamic setting where jobs both arrive and depart. Each job can only be assigned to a subset of machines and can be reassigned at any time step. The goal is to maintain a near-optimal maximum load at all time steps with a small total number of reassignments. We consider the setting where the degree of the jobs (number of machines they can be assigned to) is bounded. This is motivated by natural settings where jobs can only be locally ass...