-
作者：Dey, Santanu S.; Khajavirad, Aida
作者单位：Georgia Institute of Technology; University System of Georgia; Georgia Institute of Technology; Lehigh University
摘要：We consider the problem of minimizing a sparse nonconvex quadratic function over the unit hypercube. By developing an extension of the Reformulation-Linearization Technique (RLT) to continuous quadratic sets, we propose a novel second-order cone (SOC) representable relaxation for this problem. By exploiting the sparsity of the quadratic function, we establish a sufficient condition under which the convex hull of the feasible region of the lifted quadratic program is SOC-representable. While th...
-
作者：Gallego, Guillermo; Segev, Danny
作者单位：The Chinese University of Hong Kong, Shenzhen; Tel Aviv University; Tel Aviv University
摘要：In the adaptive ProbeTopK problem, given a collection of mutually independent random variables X1,..., Xn, our goal is to design an adaptive probing policy to sample these variables in a sequence of T stages, with the objective ofmaximizing the expected sum of the K highest rewards sampled. In spite of its stylized formulation, this setting captures numerous technical hurdles inherent to stochastic optimization, related to both information structure and efficient computation. For these reasons...
-
作者：Cembrano, Javier; Correa, Jose; Griesbach, Svenja M.; Verdugo, Victor
摘要：Traditionally, the problem of apportioning the seats of a legislative body has been viewed as a one-shot process with no dynamic considerations. While this approach is reasonable for some instances of the problem, dynamic aspects play an important role in many others. In this paper, we initiate the study of apportionment problems in an online setting. Specifically, we introduce an online algorithmic framework to handle proportional apportionment with no information about future events. In this...
-
作者：Jiang, Ruichen; Mokhtari, Aryan
作者单位：University of Texas System; University of Texas Austin
摘要：In this paper, we propose a quasi-Newton method for solving smooth and monotone nonlinear equations, including unconstrained minimization and minimax optimization as special cases. For the strongly monotone setting, we establish two global convergence bounds: (i) a linear convergence rate that matches the rate of the celebrated extragradient method, and (ii) an explicit global superlinear convergence rate that provably surpasses the linear convergence rate after at most O(d) iterations, where ...
-
作者：Warme, David M.
摘要：Strength is an important property of inequalities used in integer and mixed-integer optimization, both in theory and practice. Unfortunately, no good formal characterization for strength exists, nor is it well-understood. The first paper explored two quantitative strength indicators (extreme point ratio (EPR) and centroid distance (CD)), applying them to the subtour inequalities of the spanning tree in hypergraph polytope STHGP(n)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{w...
-
作者：Byrka, Jaroslaw; Vygen, Jens
作者单位：University of Wroclaw; University of Bonn; University of Bonn
-
作者：Soma, Tasuku; Tung, Kam Chuen; Yoshida, Yuichi
作者单位：Research Organization of Information & Systems (ROIS); Institute of Statistical Mathematics (ISM) - Japan; University of Waterloo; Research Organization of Information & Systems (ROIS); National Institute of Informatics (NII) - Japan
摘要：We provide the first online algorithm for spectral hypergraph sparsification. In the online setting, hyperedges with positive weights are arriving in a stream, and upon the arrival of each hyperedge, we must irrevocably decide whether or not to include it in the sparsifier. Our algorithm produces an (epsilon,delta)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \set...
-
作者：Pulyassary, Haripriya; Kollias, Kostas; Schild, Aaron; Shmoys, David; Wu, Manxi
作者单位：Cornell University; Alphabet Inc.; Google Incorporated; University of California System; University of California Berkeley
摘要：In this article, we introduce new models and algorithms that extend the classical network flow problems to the setting with electric vehicles (EV) that accommodate EV-specific constraints such as range limitations, charging strategies, and station capacities. Our work focuses on solving three key problems: single EV optimal charging strategy, maximum EV flow, and minimum-cost EV flow, each central to the efficient operation of EV routing systems. We establish the computational complexity of th...
-
作者：Lovitz, Benjamin; Johnston, Nathaniel
作者单位：Northeastern University; Mount Allison University
摘要：We introduce a convergent hierarchy of lower bounds on the minimum value of a real form over the unit sphere. The main practical advantage of our hierarchy over the real sum-of-squares (RSOS) hierarchy is that the lower bound at each level of our hierarchy is obtained by a minimum eigenvalue computation, as opposed to the full semidefinite program (SDP) required at each level of RSOS. In practice, this allows us to compute bounds on much larger forms than are computationally feasible for RSOS....
-
作者：Cornuejols, Gerard; Dubey, Yatharth
作者单位：Carnegie Mellon University; University of Illinois System; University of Illinois Urbana-Champaign
摘要：In this note, we consider a theoretical framework for comparing branch-and-bound with classical lift-and-project hierarchies. We simplify our analysis by streamlining the definition of branch-and-bound. We introduce skewed k-trees which give a hierarchy of relaxations that is incomparable to that of Sherali-Adams, and we show that it is much better for some instances. We also give an example where lift-and-project does very well and branch-and-bound does not. Finally, we study the set of branc...
