-
作者：Bilo, Vittorio; Moscardelli, Luca; Vinci, Cosimo
作者单位：University of Salento; G d'Annunzio University of Chieti-Pescara; Gran Sasso Science Institute (GSSI)
摘要：Motivated by possible applications in fault-tolerant selfish routing, we introduce the notion of uniform mixed equilibrium in network congestion games with adversarial link failures, where agents need to route traffic from a source to a destination node. Given an integer p >_ 1, a p-uniform mixed strategy is a mixed strategy in which an agent plays exactly p edge-disjoint paths with uniform probability; therefore, a p-uniform mixed equilibrium is a tuple of p-uniform mixed strategies, one for ...
-
作者：Chen, Xin; Stolyar, Alexander L.; Xin, Linwei
作者单位：University System of Georgia; Georgia Institute of Technology; University of Illinois System; University of Illinois Urbana-Champaign; University of Illinois System; University of Illinois Urbana-Champaign; University of Chicago
摘要：We consider a classic joint pricing and inventory control problem with lead times, which is extensively studied in the literature but is notoriously difficult to solve because of the complex structure of the optimal policy. In this work, rather than analyzing the optimal policy, we propose a class of constant-order dynamic pricing policies, which are fundamentally different from base-stock list price policies, the primary emphasis in the existing literature. Under such a policy, a constant-ord...
-
作者：Zhu, Daoli; Zhao, Lei; Zhang, Shuzhong
作者单位：Shanghai Jiao Tong University; Shanghai Jiao Tong University; The Chinese University of Hong Kong, Shenzhen; Shenzhen Research Institute of Big Data; Shanghai Jiao Tong University; Shanghai Jiao Tong University; University of Minnesota System; University of Minnesota Twin Cities
摘要：Nonlinearly constrained nonconvex and nonsmooth optimization models play an increasingly important role in machine learning, statistics, and data analytics. In this paper, based on the augmented Lagrangian function, we introduce a flexible first-order primal-dual method, to be called nonconvex auxiliary problem principle of augmented Lagrangian (NAPP-AL), for solving a class of nonlinearly constrained nonconvex and nonsmooth optimization problems. We demonstrate that NAPP-AL converges to a sta...
-
作者：Happach, Felix; Schulz, Andreas S.
作者单位：Technical University of Munich; Technical University of Munich
摘要：We consider single-machine scheduling problems that are natural generalizations or variations of the min-sum set-cover problem. For these scheduling problems, we give new approximation algorithms. Some of these algorithms rely on time-indexed linear programming relaxations. We show how a variant of alpha-point scheduling leads to the best known approximation ratios, including a guarantee of four for an interesting special case of the so-called generalized min-sum set-cover problem. We also mak...
-
作者：Tang, Tianyun; Toh, Kim-Chuan
作者单位：National University of Singapore; National University of Singapore
摘要：In this paper, we consider a semidefinite programming (SDP) relaxation of the quadratic knapsack problem. After applying low-rank factorization, we get a nonconvex problem, whose feasible region is an algebraic variety with certain good geometric properties, which we analyze. We derive a rank condition under which these two formulations are equivalent. This rank condition is much weaker than the classical rank condition if the coefficient matrix has certain special structures. We also prove th...
-
作者：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...
-
作者：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. ...
-
作者：Askari, Armin; d'Aspremont, Alexandre; El Ghaoui, Laurent
作者单位：University of California System; University of California Berkeley; Centre National de la Recherche Scientifique (CNRS); Universite PSL; Ecole Normale Superieure (ENS)
摘要：Because of its linear complexity, naive Bayes classification remains an attractive supervised learning method, especially in very large-scale settings. We propose a sparse version of naive Bayes, which can be used for feature selection. This leads to a combinatorial maximum-likelihood problem, for which we provide an exact solution in the case of binary data, or a bound in the multinomial case. We prove that our convex relaxation bounds become tight as the marginal contribution of additional f...
-
作者：Bauschke, Heinz H.; Moursi, Walaa M.
作者单位：University of British Columbia; University of Waterloo; Egyptian Knowledge Bank (EKB); Mansoura University
摘要：More than 40 years ago, Lions and Mercier introduced in a seminal paper the Douglas-Rachford algorithm. Today, this method is well-recognized as a classic and highly successful splitting method to find minimizers of the sum of two (not necessarily smooth) convex functions. Whereas the underlying theory has matured, one case remains a mystery: the behavior of the shadow sequence when the given functions have disjoint domains. Building on previous work, we establish for the first time weak and v...
