-
作者：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...
-
作者：Lim, Tongseok; McCann, Robert J.
作者单位：Purdue University System; Purdue University; University of Toronto
摘要：We bound the variance and other moments of a random vector based on the range of its realizations, thus generalizing inequalities of Popoviciu and of Bhatia and Davis concerning measures on the line to several dimensions. This is done using convex duality and (infinite-dimensional) linear programming. The following consequence of our bounds exhibits symmetry breaking, provides a new proof of Jung's theorem, and turns out to have applications to the aggregation dynamics modelling attractive-rep...
-
作者：Dahan, Mathieu; Amin, Saurabh; Jaillet, Patrick
作者单位：University System of Georgia; Georgia Institute of Technology; Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT)
摘要：This article poses the following problem: Does there exist a probability distribution over subsets of a finite partially ordered set (poset), such that a set of constraints involving marginal probabilities of the poset's elements and maximal chains is satisfied? We present a combinatorial algorithm to positively resolve this question. The algorithm can be implemented in polynomial time in the special case where maximal chain probabilities are affine functions of their elements. This existence ...
