-
作者：Bravo, Mario; Contreras, Juan Pablo
作者单位：Universidad de Santiago de Chile; University Diego Portales
摘要：We analyze the oracle complexity of the stochastic Halpern iteration with minibatch, where we aim to approximate fixed-points of nonexpansive and contractive operators in a normed finite-dimensional space. We show that if the underlying stochastic oracle has uniformly bounded variance, our method exhibits an overall oracle complexity of O(epsilon(-5)), to obtain expected fixed-point residual for nonexpansive operators, improving recent rates established for the stochastic Krasnoselskii-Mann it...
-
作者：Leyffer, Sven; Manns, Paul
作者单位：United States Department of Energy (DOE); Argonne National Laboratory
-
作者：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...
-
作者：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...
-
作者：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...
-
作者：Chizat, Lenaic; Delalande, Alex; Vaskevicius, Tomas
作者单位：Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne
摘要：We study the convergence rate of Sinkhorn's algorithm for solving entropy-regularized optimal transport problems when at least one of the probability measures, mu, admits a density over R-d. For a semi-concave cost function bounded by cand a regularization parameter lambda > 0, we obtain exponential convergence guarantees on the dual sub-optimality gap with contraction rates that are polynomial in lambda/c(infinity). This represents an exponential improvement over the known contraction rate 1-...
-
作者：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...
