-
作者：Zhao, Jingyang; Xiao, Mingyu
作者单位：University of Electronic Science & Technology of China
摘要：The bipartite traveling tournament problem (BTTP) addresses interleague sports scheduling, which aims to design a feasible bipartite tournament between two n-team leagues under some constraints such that the total traveling distance of all participating teams is minimized. Since its introduction, several methods have been developed to design feasible schedules for the National Basketball Association (NBA), Nippon Professional Baseball (NPB), and so on. In terms of solution quality with a theor...
-
作者：Brustle, Johannes; Perez-Salazar, Sebastian; Verdugo, Victor
作者单位：Sapienza University Rome; Rice University; Rice University; Pontificia Universidad Catolica de Chile; Pontificia Universidad Catolica de Chile
摘要：The prophet inequality is one of the cornerstone problems in optimal stopping theory and has become a crucial tool for designing sequential algorithms in Bayesian settings. In the i.i.d. k-selection prophet inequality problem, we sequentially observe n nonnegative random values sampled from a known distribution. Each time, a decision is made to accept or reject the value, and under the constraint of accepting at most k items. For k = 1, Hill and Kertz [Ann. Probab. 1982] provided an upper boun...
-
作者：Wirth, Elias; Pena, Javier; Pokutta, Sebastian
作者单位：Technical University of Berlin; Carnegie Mellon University; Zuse Institute Berlin
摘要：We provide a template to derive affine-invariant convergence rates for the following popular versions of the Frank-Wolfe algorithm on polytopes: vanilla Frank-Wolfe, Frank-Wolfe with away steps, Frank-Wolfe with blended pairwise steps, and Frank-Wolfe with in-face directions. Our template shows how the convergence rates follow from two affine-invariant properties of the problem, namely, error bound and extended curvature. These properties depend solely on the polytope and objective function bu...
-
作者：Cembrano, Javier; Fischer, Felix; Klimm, Max
作者单位：Max Planck Society; Technical University of Berlin; University of London; Queen Mary University London
摘要：A randomized selection mechanism returns a probability distribution over individuals based on mutual nominations among them; it is impartial if the selection probability of each individual is independent of the nominations they cast and alpha-optimal if the expected number of nominations received by the selected individual is always at least alpha times that received by any individual. When individuals can cast multiple nominations, the permutation mechanism is 1/2-optimal, and this is the bes...
-
作者：Jiang, Jiashuo; Ma, Will; Zhang, Jiawei
作者单位：Hong Kong University of Science & Technology; Columbia University; New York University
摘要：Prophet inequalities consist of many beautiful statements that establish tight performance ratios between online and offline allocation algorithms. Typically, tightness is established by constructing an algorithmic guarantee and a worst-case instance separately, whose bounds match as a result of some ingenuity. In this paper, we instead formulate the construction of the worst-case instance as an optimization problem, which directly finds the tight ratio without needing to construct two bounds ...
-
作者：Jezequel, Remi; Ostrovskii, Dmitrii; Gaillard, Pierre
作者单位：Inria; Universite PSL; Ecole Normale Superieure (ENS); University System of Georgia; Georgia Institute of Technology; Centre National de la Recherche Scientifique (CNRS); Communaute Universite Grenoble Alpes; Universite Grenoble Alpes (UGA); Inria; Institut National Polytechnique de Grenoble
摘要：In the problem of online portfolio selection as formulated by Cover [Cover TM (1991) Universal portfolios. Math. Finance 1(1):1-29], the trader repeatedly distributes the trader's capital over d assets in each of T > 1 rounds with the goal of maximizing the total return. Cover proposed an algorithm, termed universal portfolios, that performs nearly as well as the best (in hindsight) static assignment of a portfolio with an O(d log(T)) logarithmic regret. Without imposing any restrictions on th...
-
作者：Hajiabolhassan, Hossein; Ortner, Ronald
作者单位：Medical University of Graz; University of Leoben
摘要：We consider general reinforcement learning under the average reward criterion in Markov decision processes (MDPs), when the learner's goal is not to learn an optimal policy, but accepts any policy whose average reward is above a given satisfaction level a. We show that with this more modest objective, it is possible to give algorithms that only have constant regret with respect to the level a, provided that there is a policy above this level. This is a generalization of known results from the ...
-
作者：Segev, Danny
作者单位：Tel Aviv University; Tel Aviv University
摘要：The primary objective of this work is to revisit and revitalize one of the most fundamental models in deterministic inventory management, the continuous-time joint replenishment problem. Our main contribution consists of resolving several long-standing open questions in this context. For most of these questions, we obtain the first quantitative improvement over power-of-2 policies and their nearby derivatives, which have been state-of-the-art in terms of provable performance guarantees since t...
-
作者：Zhang, Chuwen; He, Chang; Jiang, Yuntian; Xue, Chenyu; Jiang, Bo; Ge, Dongdong; Ye, Yinyu
作者单位：Shanghai University of Finance & Economics; Shanghai University of Finance & Economics; Shanghai University of Finance & Economics; Shanghai Jiao Tong University; Stanford University
摘要：In this paper, we introduce a homogeneous second-order descent method (HSODM) motivated from the homogenization trick in quadratic programming. The merit of homogenization is that only the leftmost eigenvector of a gradient-Hessian integrated matrix is computed at each iteration. Therefore, the algorithm is a single-loop method that does not need to switch to other sophisticated algorithms and is easy to implement. We show that HSODM has a global convergence rate of O(epsilon-3=2) to find an e...
-
作者：Akrami, Hannaneh; Chaudhury, Bhaskar Ray; Hoefer, Martin; Mehlhorn, Kurt; Schmalhofer, Marco; Shahkarami, Golnoosh; Varricchio, Giovanna; Vermande, Quentin; van Wijland, Ernest
作者单位：Max Planck Society; University of Bonn; Saarland University; University of Illinois System; University of Illinois Urbana-Champaign; University of Illinois System; University of Illinois Urbana-Champaign; RWTH Aachen University; Goethe University Frankfurt; Saarland University; University of Calabria; Universite Cote d'Azur; Universite Paris Cite
摘要：We study the problem of allocating a set of indivisible goods among a set of agents with two-value additive valuations. In this setting, each good is valued either 1 or psq for some fixed coprime numbers p,q E N such that 1 <= q <= p. Our goal is to find an allocation that maximizes the Nash social welfare (NSW), that is, the geometric mean of the valuations of the agents. In this work, we give a complete characterization of polynomial-time tractability of NSW maximization that solely depends ...
