-
作者：Blanchet, Jose; Murthy, Karthyek; Zhang, Fan
作者单位：Stanford University; Singapore University of Technology & Design
摘要：We consider optimal transport-based distributionally robust optimization (DRO) problems with locally strongly convex transport cost functions and affine decision rules. Under conventional convexity assumptions on the underlying loss function, we obtain structural results about the value function, the optimal policy, and the worst-case optimal transport adversarial model. These results expose a rich structure embedded in the DRO problem (e.g., strong convexity even if the non-DRO problem is not...
-
作者：Basei, Matteo; Cao, Haoyang; Guo, Xin
作者单位：University of California System; University of California Berkeley; Electricite de France (EDF); Alan Turing Institute
摘要：We consider a general class of nonzero-sum N-player stochastic games with impulse controls, where players control the underlying dynamics with discrete interventions. We adopt a verification approach and provide sufficient conditions for the Nash equilibria (NEs) of the game. We then consider the limiting situation when N goes to infinity, that is, a suitable mean-field game (MFG) with impulse controls. We show that under appropriate technical conditions, there exists a unique NE solution to t...
-
作者：Gutekunst, Samuel C.; Williamson, David P.
作者单位：Bucknell University; Bucknell University; Cornell University
摘要：The traveling salesman problem (TSP) is a fundamental problem in combinatorial optimization. Several semidefinite programming relaxations have been proposed recently that exploit a variety of mathematical structures including, for example, algebraic connectivity, permutation matrices, and association schemes. The main results of this paper are twofold. First, de Klerk and Sotirov [de Klerk E, Sotirov R (2012) Improved semidefinite programming bounds for quadratic assignment problems with suita...
-
作者：Klimm, Max; Schuetz, Andreas
作者单位：Technical University of Berlin
摘要：This paper studies the existence of pure Nash equilibria in atomic congestion games with different user classes where the cost of each resource depends on the aggregated demand of each class. A set of cost functions is called consistent for this class if all games with cost functions from the set have a pure Nash equilibrium. We give a complete characterization of consistent sets of cost functions showing that the only consistent sets of cost functions are sets of certain affine functions and ...
-
作者：Perez-Salazar, Sebastian; Singh, Mohit; Toriello, Alejandro
作者单位：University System of Georgia; Georgia Institute of Technology
摘要：Motivated by bursty bandwidth allocation and by the allocation of virtual machines to servers in the cloud, we consider the online problem of packing items with random sizes into unit-capacity bins. Items arrive sequentially, but on arrival, an item's actual size is unknown; only its probabilistic information is available to the decision maker. Without knowing this size, the decision maker must irrevocably pack the item into an available bin or place it in a new bin. Once packed in a bin, the ...
-
作者：Amarante, Massimiliano
作者单位：Universite de Montreal; Universite de Montreal
摘要：After showing, by means of a series of examples, that paradigms alternative to the Bayesian one obtain by simply replacing the notion of approximation associated with the latter, the paper presents a unified framework for theories of decision making and inference. Given a statistical model, the algebra of bounded random variables on the sample space is mapped homomorphically into an algebra of operators on a certain Hilbert space. Then, the choice of a norm or a divergence function on the latt...
-
作者：Puha, Amber L.; Ward, Amy R.
作者单位：California State University System; California State University San Marcos; University of Chicago
摘要：We describe a fluid model with time-varying input that approximates a multiclass many-server queue with general reneging distribution and multiple customer classes (specifically, the multiclass G/GI/N+GI queue). The system dynamics depend on the policy, which is a rule for determining when to serve a given customer class. The class of admissible control policies are those that are head-of-the-line (HL) and nonanticipating. For a sequence of many-server queues operating under admissible HL cont...
-
作者：Bai, Kuang; Ye, Jane J.
作者单位：Hong Kong Polytechnic University; University of Victoria
摘要：The bilevel program is an optimization problem in which the constraint involves solutions to a parametric optimization problem. It is well known that the value function reformulation provides an equivalent single-level optimization problem, but it results in a non-smooth optimization problem that never satisfies the usual constraint qualification, such as the Mangasarian-Fromovitz constraint qualification (MFCQ). In this paper, we show that even the first order sufficient condition for metric ...
-
作者：Chen, Ningyuan; Gallego, Guillermo
作者单位：University of Toronto; Hong Kong University of Science & Technology
摘要：We consider the problem of a firm seeking to use personalized pricing to sell an exogenously given stock of a product over a finite selling horizon to different consumer types. We assume that the type of an arriving consumer can be observed, but the demand function associated with each type is initially unknown. The firm sets personalized prices dynamically for each type and attempts to maximize the revenue over the season. We provide a learning algorithm that is near optimal when the demand a...
-
作者：Chandrasekaran, Karthekeyan; Chekuri, Chandra
作者单位：University of Illinois System; University of Illinois Urbana-Champaign
摘要：We consider the HYPERGRAPH-k-CUT problem. The input consists of a hypergraph G = (V, E) with nonnegative hyperedge-costs c : E ??? R+ and a positive integer k. The objective is to find a minimum cost subset F ??? E such that the number of connected components in G ??? F is at least k. An alternative formulation of the objective is to find a partition of V into k nonempty sets V1, V2, ..., Vk so as to minimize the cost of the hyperedges that cross the partition. GRAPH-k-CUT, the special case of...
