-
作者：Marinkovic, Javier; Soto, Jose A.; Verdugo, Victor
作者单位：Universidad de Chile; Universidad de Chile; Pontificia Universidad Catolica de Chile; Pontificia Universidad Catolica de Chile; University System of Maryland; University of Maryland College Park
摘要：We consider an online multi-weighted generalization of several classic online optimization problems called the online combinatorial assignment problem. We are given an independence system over a ground set of elements and agents that arrive online one by one. Upon arrival, each agent reveals a weight function over the elements of the ground set. If the independence system is given by the matchings of a hypergraph, we recover the combinatorial auction problem, where every node represents an ite...
-
作者：Klimm, Max; Knaack, Martin
作者单位：Technical University of Berlin
摘要：We study different online optimization problems in the random-order model. There is a finite set of bins with known capacities and a finite set of items arriving in uniform random order. Upon arrival of an item, its size and its value for each of the bins is revealed and it has to be decided immediately and irrevocably to which bin the item is assigned, or whether the item is rejected. In this setting, an algorithm is alpha -competitive if the total expected value of all items assigned to the ...
-
作者：Armbruster, Alexander; Grandoni, Fabrizio; Husic, Edin; Tinguely, Antoine; Wiese, Andreas
作者单位：Technical University of Munich; Universita della Svizzera Italiana
摘要：In the Time-Windows Unsplittable Flow on a Path problem (twUFP) we are given a resource whose available amount changes over a given time interval (modeled as the edge-capacities of a given path G) and a collection of tasks. Each task is characterized by a demand (of the considered resource), a profit, an integral processing time, and a time window. Our goal is to compute a maximum profit subset of tasks and schedule them non-preemptively within their respective time windows, such that the tota...
-
作者：Heimendahl, Arne; Lucke, Moritz; Vallentin, Frank; Zimmermann, Marc Christian
作者单位：University of Cologne
摘要：We derive and analyze an infinite-dimensional semidefinite program which computes least distortion embeddings of flat tori Rn/L\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathbb {R}<^>n/L$$\end{document}, where L is an n-dimensional lattice, into Hilbert spaces. This enables us to provide a constant factor imp...
-
作者：Jin, Qing; Georghiou, Angelos; Vayanos, Phebe; Hanasusanto, Grani A.
作者单位：University of Southern California; University of Southern California; University of Cyprus; University of Southern California; University of Illinois System; University of Illinois Urbana-Champaign
摘要：We study two-stage distributionally robust optimization (DRO) problems with decision-dependent information discovery (DDID) wherein (a portion of) the uncertain parameters are revealed only if an (often costly) investment is made at the first stage. This class of problems finds many important applications in selection problems (e.g., in hiring, project portfolio optimization, or optimal sensor location). Despite the wide applicability of the problem, it has not been previously studied. We prop...
-
作者：Chen, Lin; Lian, Jiayi; Mao, Yuchen; Zhang, Guochuan
作者单位：Zhejiang University
摘要：We investigate pseudo-polynomial time algorithms for Subset Sum. Given a multi-set X consisting of n positive integers and a target t, Subset Sum asks whether some subset of X sums to t. Bringmann proposed an O(n +t)-time algorithm [Bringmann SODA'17].An open question has naturally arisen: can Subset Sum be solved in O(n+ w)time? Here w is the largest integer in X. We make progress towards resolving the open question by proposing an O(n + root wt)-time algorithm.
-
作者：Brosch, Daniel; Puges, Diane
作者单位：University of Klagenfurt
摘要：The inducibility of a graph represents its maximum density as an induced subgraph over all possible sequences of graphs of size growing to infinity. This invariant of graphs has been extensively studied since its introduction in 1975 by Pippenger and Golumbic. In 2017, Czabarka, Sz & eacute;kely and Wagner extended this notion to leaf-labeled rooted binary trees, which are objects widely studied in the field of phylogenetics. They obtain the first results and bounds for the densities and induc...
-
作者：Jin, Qiujiang; Jiang, Ruichen; Mokhtari, Aryan
作者单位：University of Texas System; University of Texas Austin
摘要：In this paper, we explore the non-asymptotic global convergence rates of the Broyden-Fletcher-Goldfarb-Shanno (BFGS) method implemented with exact line search. Notably, due to Dixon's equivalence result, our findings are also applicable to other quasi-Newton methods in the convex Broyden class employing exact line search, such as the Davidon-Fletcher-Powell (DFP) method. Specifically, we focus on problems where the objective function is strongly convex with Lipschitz continuous gradient and He...
-
作者：Catanzaro, Daniele; Pesenti, Raffaele; Sapucaia, Allan; Wolsey, Laurence
作者单位：Universite Catholique Louvain; Universita Ca Foscari Venezia
摘要：Path-Length Matrices (PLMs) form a tree encoding scheme that is often used in the context of optimization problems defined over Unrooted Binary Trees (UBTs). Determining the conditions that a symmetric integer matrix of order n >= 3 must satisfy to encode the PLM of a UBT with n leaves is central to these applications. Here, we show that a certain subset of known necessary conditions is also sufficient to characterize the set Theta(n) of PLMs induced by the set of UBTs with n leaves. We also i...
-
作者：Luner, Alan; Grimmer, Benjamin
作者单位：Johns Hopkins University
摘要：We extend recent computer-assisted design and analysis techniques for first-order optimization over structured functions-known as performance estimation-to apply to structured sets. We prove interpolation theorems for smooth and strongly convex sets with interior point conditions and bounded diameter, showing a wide range of extremal questions amount to structured mathematical programs. Prior function interpolation theorems are recovered as a limit of our set interpolation theory. Our theory p...
