-
作者：Celaya, Marcel; Kuhlmann, Stefan; Paat, Joseph; Weismantel, Robert
作者单位：Cardiff University; Technical University of Berlin; University of British Columbia
摘要：This paper deals with linear integer optimization. We develop a technique that can be applied to provide improved upper bounds for two important questions in linear integer optimization. Given an optimal vertex solution for the linear relaxation, how far away is the nearest optimal integer solution (if one exists; proximity bounds)? If a polyhedron contains no integer point, what is the smallest number of integer parallel hyperplanes defined by an integral, nonzero, normal vector that intersec...
-
作者：Chen, Xujin; Ding, Guoli; Zang, Wenan; Zhao, Qiulan
作者单位：Chinese Academy of Sciences; Academy of Mathematics & System Sciences, CAS; Chinese Academy of Sciences; University of Chinese Academy of Sciences, CAS; Louisiana State University System; Louisiana State University; University of Hong Kong; Nanjing University
摘要：Let T = (V,A) be a tournament with a nonnegative integral weight w(e) on each arc e. A subset F of arcs is called a feedback arc set (FAS) if T\F contains no cycles (directed). A collection F of FASs (with repetition allowed) is called an FAS packing if each arc e is used at most w(e) times by the members of F. The purpose of this paper is to give a characterization of all tournaments T = (V,A) with the property that, for every nonnegative integral weight function w defined on A, the minimum t...
-
作者：Blauth, Jannis; Neuwohner, Meike; Puhlmann, Luise; Vygen, Jens
作者单位：University of Bonn; University of London; London School Economics & Political Science
摘要：We revisit the A PRIORI TSP (with independent activation) and prove stronger approximation guarantees than were previously known. In the A PRIORI TSP, we are given a metric space (V, c ) and an activation probability p ( v ) for each customer v is an element of V . We ask for a TSP tour T for V that minimizes the expected length after cutting T short by skipping the inactive customers. All known approximation algorithms select a nonempty subset S of the customers and construct a master route s...
-
作者：Bolte, Jerome; Combettes, Cyrille W.; Pauwelsb, Edouard
作者单位：Universite de Toulouse; Universite Toulouse 1 Capitole; Toulouse School of Economics; Universite de Toulouse; Universite Toulouse 1 Capitole; Toulouse School of Economics; Institut Universitaire de France
摘要：The Frank-Wolfe algorithm is a popular method for minimizing a smooth convex function f over a compact convex set C. Whereas many convergence results have been derived in terms of function values, almost nothing is known about the convergence behavior of the sequence of iterates (xt)t is an element of N. Under the usual assumptions, we design several counterexamples to the convergence of (xt)t is an element of N, where f is d-time continuously differentiable, dP 2, and f(xt) -> minC f. Our cou...
-
作者：Fu, Guanxing; Horst, Ulrich; Xia, Xiaonyu
作者单位：Hong Kong Polytechnic University; Hong Kong Polytechnic University; Humboldt University of Berlin; Humboldt University of Berlin; Wenzhou University
摘要：We consider a mean-field control problem with ca`dla`g semimartingale strategies arising in portfolio liquidation models with transient market impact and self-exciting order flow. We show that the value function depends on the state process only through its law, and we show that it is of linear-quadratic form and that its coefficients satisfy a coupled system of nonstandard Riccati-type equations. The Riccati equations are obtained heuristically by passing to the continuous-time limit from a s...
-
作者：Rutten, Daan; Mukherjee, Debankur
作者单位：University System of Georgia; Georgia Institute of Technology
摘要：Modern data centers suffer from immense power consumption. As a result, data center operators have heavily invested in capacity-scaling solutions, which dynamically deactivate servers if the demand is low and activate them again when the workload increases. We analyze a continuous-time model for capacity scaling, where the goal is to minimize the weighted sum of flow time, switching cost, and power consumption in an online fashion. We propose a novel algorithm, called adaptive balanced capacit...
-
作者：Doval, Laura; Skreta, Vasiliki
作者单位：Columbia University; Centre for Economic Policy Research - UK; University of Texas System; University of Texas Austin; University of London; University College London
摘要：We provide tools to analyze information design problems subject to constraints. We do so by extending an insight by Le Treust and Tomala to the case of multiple inequality and equality constraints. Namely, that an information design problem subject to constraints can be represented as an unconstrained information design problem with additional states, one for each constraint. Thus, without loss of generality, optimal solutions induce as many posteriors as the number of states and constraints. ...
-
作者：Bayraktar, Erhan; Huang, Yu-Jui; Wang, Zhenhua; Zhou, Zhou
作者单位：University of Michigan System; University of Michigan; University of Colorado System; University of Colorado Boulder; Shandong University; Shandong University; University of Sydney
摘要：This paper considers an infinite-horizon Markov decision process (MDP) that allows for general nonexponential discount functions in both discrete and continuous time. Because of the inherent time inconsistency, we look for a randomized equilibrium policy (i.e., relaxed equilibrium) in an intrapersonal game between an agent's current and future selves. When we modify the MDP by entropy regularization, a relaxed equilibrium is shown to exist by a nontrivial entropy estimate. As the degree of reg...
-
作者：Kwon, H. Dharma; Palczewski, Jan
作者单位：University of Illinois System; University of Illinois Urbana-Champaign; University of Leeds
摘要：The timing of strategic exit is one of the most important but difficult business decisions, especially under competition and uncertainty. Motivated by this problem, we examine a stochastic game of exit in which players are uncertain about their competitor's exit value. We construct an equilibrium for a large class of payoff flows driven by a general one-dimensional diffusion. In the equilibrium, the players employ sophisticated exit strategies involving both the state variable and the posterio...
-
作者：Vazirani, Vijay V.
作者单位：University of California System; University of California Irvine
摘要：The Micali-Vazirani (MV) algorithm for finding a maximum cardinality matching in general graphs, which was published in 1980, remains to this day the most efficient known algorithm for the problem. The current paper gives the first complete and correct proof of this algorithm. The MV algorithm resorts to finding minimum-length augmenting paths. However, such paths fail to satisfy an elementary property, called breadth first search honesty in this paper. In the absence of this property, an expo...
