-
作者：Chandrasekaran, Karthekeyan; Chekuri, Chandra; Fiorini, Samuel; Kulkarni, Shubhang; Weltge, Stefan
作者单位：University of Illinois System; University of Illinois Urbana-Champaign; Universite Libre de Bruxelles; Technical University of Munich
摘要：We consider the feedback vertex set problem in undirected graphs (FVS). The input to FVS is an undirected graph G=(V,E) with non-negative vertex costs. The goal is to find a minimum cost subset of vertices S subset of V such that G-S is acyclic. FVS is a well-known NP-hard problem and does not admit a (2-& varepsilon;)-approximation for any fixed & varepsilon;>0 assuming the Unique Games Conjecture. There are combinatorial 2-approximation algorithms (Bafna et al., in: Algorithms and computatio...
-
作者：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...
-
作者：Wang, Guanghui; Hu, Zihao; Gentile, Claudio; Muthukumar, Vidya; Abernethy, Jacob
作者单位：University System of Georgia; Georgia Institute of Technology; Alphabet Inc.; Google Incorporated; Alphabet Inc.; Google Incorporated; Hong Kong University of Science & Technology
摘要：First-order optimization methods tend to inherently favor certain solutions over others when minimizing an underdetermined training objective that has multiple global optima. This phenomenon, known as implicit bias, plays a critical role in understanding the generalization capabilities of optimization algorithms. Recent research has revealed that in separable binary classification tasks gradient-descent-based methods exhibit an implicit bias for the & ell;2\documentclass[12pt]{minimal} \usepac...
-
作者：Balogh, Janos; Cohen, Ilan Reuven; Epstein, Leah; Levin, Asaf
作者单位：Szeged University; Bar Ilan University; University of Haifa; Technion Israel Institute of Technology
摘要：In this work, we consider online d-dimensional vector bin packing. For this problem, it is known that no algorithm can have a competitive ratio of o(d/log2d)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$o(d/\log <^>2 d)$$\end{document} in the absolute sense, although upper bounds for it are typically presented in...
-
作者：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....
