-
作者：Giannakopoulos, Yiannis; Noarov, Georgy; Schulz, Andreas S.
作者单位：University of Erlangen Nuremberg; University of Pennsylvania; Technical University of Munich
摘要：We present a deterministic polynomial-time algorithm for computing d(d+o(d))-approximate (pure) Nash equilibria in (proportional sharing) weighted congestion games with polynomial cost functions of degree at most d. This is an exponential improvement of the approximation factor with respect to the previously best deterministic algorithm. An appealing additional feature of the algorithm is that it only uses best-improvement steps in the actual game, as opposed to the previously best algorithms,...
-
作者：Atar, Rami; Budhiraja, Amarjit; Dupuis, Paul; Wu, Ruoyu
作者单位：Technion Israel Institute of Technology; University of North Carolina; University of North Carolina Chapel Hill; Brown University; Iowa State University
摘要：For the M/M/1+M model at the law-of-large-numbers scale, the long-run reneging count per unit time does not depend on the individual (i.e., per customer) reneging rate. This paradoxical statement has a simple proof. Less obvious is a large deviations analogue of this fact, stated as follows: the decay rate of the probability that the long-run reneging count per unit time is atypically large or atypically small does not depend on the individual reneging rate. In this paper, the sample path larg...
-
作者：Lange, Daniela Andrea Hurtado; Maguluri, Siva Theja
作者单位：William & Mary; University System of Georgia; Georgia Institute of Technology
摘要：We study the heavy-traffic limit of the generalized switch operating under Max-Weight, without assuming that the complete resource pooling condition is satisfied and allowing for correlated arrivals. The main contribution of this paper is the steady-state mean of linear combinations of queue lengths in heavy traffic. We showcase the generality of our result by presenting various stochastic networks as corollaries, each of which is a contribution by itself. In particular, we study the input-que...
-
作者：Goldberg, Paul W.; Hollender, Alexandros; Igarashi, Ayumi; Manurangsi, Pasin; Suksompong, Warut
作者单位：University of Oxford; Research Organization of Information & Systems (ROIS); National Institute of Informatics (NII) - Japan; Alphabet Inc.; Google Incorporated; National University of Singapore
摘要：Consensus halving refers to the problem of dividing a resource into two parts so that every agent values both parts equally. Prior work shows that, when the resource is represented by an interval, a consensus halving with at most n cuts always exists but is hard to compute even for agents with simple valuation functions. In this paper, we study consensus halving in a natural setting in which the resource consists of a set of items without a linear ordering. For agents with linear and additivel...
-
作者：Alaluf, Naor; Ene, Alina; Feldman, Moran; Nguyen, Huy L.; Suh, Andrew
作者单位：Open University Israel; Boston University; University of Haifa; Northeastern University
摘要：We study the problem of maximizing a nonmonotone submodular function subject to a cardinality constraint in the streaming model. Our main contribution is a singlepass (semi) streaming algorithm that uses roughly O(k/epsilon(2)) memory, where k is the size constraint. At the end of the stream, our algorithm postprocesses its data structure using any off-line algorithm for submodular maximization and obtains a solution whose approximation guarantee is alpha/(1 + alpha) - epsilon, where a is the ...
-
作者：Liu, Jia; Lisser, Abdel; Chen, Zhiping
作者单位：Xi'an Jiaotong University; Universite Paris Saclay; Centre National de la Recherche Scientifique (CNRS)
摘要：This paper discusses distributionally robust geometric programs with individual or joint chance constraints. Several groups of uncertainty sets are considered: uncertainty sets with first two order moments information; uncertainty sets with known first order or first two order moments information under nonnegative support; uncertainty sets constrained by the Kullback-Leibler divergence with a normal or discrete reference distribution; uncertainty sets constrained by the Wasserstein distance un...
-
作者：Hildebrand, Roland
作者单位：Communaute Universite Grenoble Alpes; Institut National Polytechnique de Grenoble; Universite Grenoble Alpes (UGA); Centre National de la Recherche Scientifique (CNRS); Inria; Moscow Institute of Physics & Technology
摘要：Self-concordance is the most important property required for barriers in convex programming. It is intrinsically linked to the affine structure of the underlying space. Here we introduce an alternative notion of self-concordance that is linked to the projective structure. A function on a set X in an affine space is projectively self-concordant if and only if it can be extended to an affinely self-concordant logarithmically homogeneous function on the conic extension of X. The feasible sets in ...
-
作者：Correa, Jose; Cristi, Andres; Oosterwijk, Tim
作者单位：Universidad de Chile; Vrije Universiteit Amsterdam
摘要：Dynamic network flows, or network flows over time, constitute an important model for real-world situations in which steady states are unusual, such as urban traffic and the internet. These applications immediately raise the issue of analyzing dynamic network flows from a game-theoretic perspective. In this paper, we study dynamic equilibria in the deterministic fluid queuing model in single-source, single-sink networks-arguably the most basic model for flows over time. In the last decade, we h...
-
作者：Yu, Huizhen
作者单位：University of Alberta
摘要：We consider the linear programming approach for constrained and unconstrained Markov decision processes (MDPs) under the long-run average-cost criterion, where the class of MDPs in our study have Borel state spaces and discrete countable action spaces. Under a strict unboundedness condition on the one-stage costs and a recently introduced majorization condition on the state transition stochastic kernel, we study infinite-dimensional linear programs for the average-cost MDPs and prove the absen...
-
作者：Towle, Eli; Luedtke, James
作者单位：University of Wisconsin System; University of Wisconsin Madison
摘要：We present a framework to obtain valid inequalities for a reverse convex set: the set of points in a polyhedron that lie outside a given open convex set. Reverse convex sets arise in many models, including bilevel optimization and polynomial optimization. An intersection cut is a well-known valid inequality for a reverse convex set that is generated from a basic solution that lies within the convex set. We introduce a framework for deriving valid inequalities for the reverse convex set from ba...
