-
作者：Anthony, Barbara; Goyal, Vineet; Gupta, Anupam; Nagarajan, Viswanath
作者单位：Massachusetts Institute of Technology (MIT); Carnegie Mellon University; International Business Machines (IBM); IBM USA
摘要：This paper studies an extension of the k-median problem under uncertain demand. We are given an n-vertex metric space (V, d) and m client sets {S-i subset of V}(i=1)(m). The goal is to open a set of k facilities F such that the worst-case connection cost over all the client sets is minimized, i.e., min(F subset of V,vertical bar F vertical bar=k) max(i is an element of[m]){Sigma(d(j,f))(j is an element of si)}, where for any F subset of V, d(j, F) = min(f is an element of F) d(j, f). This is a...
-
作者：Bogomolnaia, Anna; Holzman, Ron; Moulin, Herve
作者单位：Rice University; Technion Israel Institute of Technology
摘要：We consider a communication network where each pair of users requests a connection guaranteeing a certain capacity. The cost of building capacity is identical across pairs. Efficiency is achieved by any maximal cost spanning tree. We construct cost sharing methods ensuring standalone core stability, monotonicity of one's cost share in one's capacity requests, and continuity in everyone's requests. We define a solution for simple problems where each pairwise request is zero or one, and extend i...
-
作者：Bayraktar, Erhan; Egami, Masahiko
作者单位：University of Michigan System; University of Michigan; Kyoto University
摘要：We explicitly solve the optimal switching problem for one-dimensional diffusions by directly using the dynamic programming principle and the excessive characterization of the value function. The shape of the value function and the smooth fit principle then can be proved using the properties of concave functions.
-
作者：Dobzinski, Shahar; Nisan, Noam; Schapira, Michael
作者单位：Cornell University; Hebrew University of Jerusalem; Yale University; University of California System; University of California Berkeley
摘要：In a combinatorial auction m heterogenous indivisible items are sold to n bidders. This paper considers settings in which the valuation functions of the bidders are known to be complement free (a.k.a. subadditive). We provide several approximation algorithms for the social-welfare maximization problem in such settings. First, we present a logarithmic upper bound for the case that the access to the valuation functions is via demand queries. For the weaker value queries model we provide a tight ...
-
作者：Flesch, J.; Kuipers, J.; Schoenmakers, G.; Vrieze, K.
作者单位：Maastricht University; Maastricht University
摘要：We consider a class of n-player stochastic games with the following properties: (1) in every state, the transitions are controlled by one player; (2) the payoffs are equal to zero in every nonabsorbing state; (3) the payoffs are nonnegative in every absorbing state. We propose a new iterative method to analyze these games. With respect to the expected average reward, we prove the existence of a subgame-perfect epsilon-equilibrium in pure strategies for every epsilon > 0. Moreover, if all trans...
-
作者：Goberna, M. A.; Terlaky, T.; Todorov, M. I.
作者单位：Universitat d'Alacant; Lehigh University; Bulgarian Academy of Sciences; Universidad Americas Puebla (UDLAP)
摘要：This paper provides sufficient conditions for the optimal value function of a given linear semi-infinite programming (LSIP) problem to depend linearly on the size of the perturbations, when these perturbations involve either the cost coefficients or the right-hand side function or both, and they are sufficiently small. Two kinds of partitions are considered. The first concerns the effective domain of the optimal value as a function of the cost coefficients and consists of maximal regions on wh...
-
作者：Andersen, Kent; Louveaux, Quentin; Weismantel, Robert
作者单位：Otto von Guericke University; University of Liege
摘要：A maximal lattice free polyhedron L has max-facet-width equal to w if max(x is an element of L) pi(T) x-min(x is an element of L) pi(T) x <= w for all facets pi(T) x <= pi(0) of L, and max(x is an element of L) pi(T) x-min(x is an element of L) pi(T) x = w for some facet pi(T) x <= pi(0) of L. The set obtained by adding all cuts whose validity follows from a maximal lattice free polyhedron with max-facet-width at most w is called the wth split closure. We show the wth split closure is a polyhe...
-
作者：Lu, Shu
作者单位：University of North Carolina; University of North Carolina Chapel Hill
摘要：This paper studies solution properties of a parametric variational condition under the constant rank constraint qualification (CRCQ), and properties of its underlying set. We start by showing that if the CRCQ holds at a point in a fixed set, then there exists a one-to-one correspondence between the collection of nonempty faces of the normal cone to the set at that point and the collection of active index sets at points nearby. We then study the behavior of the Euclidean projector, and prove un...
