-
作者：Bandi, Chaithanya; Bertsimas, Dimitris
作者单位：Northwestern University; Massachusetts Institute of Technology (MIT)
摘要：In this paper, we revisit the auction design problem for multi-item auctions with budget constrained buyers by introducing a robust optimization approach to model (a) concepts such as incentive compatibility and individual rationality that are naturally expressed in the language of robust optimization and (b) the auctioneer's beliefs on the buyers' valuations of the items. Rather than using probability distributions (the classical probabilistic approach) or an adversarial model to model valuat...
-
作者：Alpern, Steve; Lidbetter, Thomas
作者单位：University of Warwick; University of London; London School Economics & Political Science
摘要：A point lies on a network according to some unknown probability distribution. Starting at a specified root of the network, a Searcher moves to find this point at speeds that depend on his location and direction. He seeks the randomized search algorithm that minimizes the expected search time. This is equivalent to modeling the problem as a zero-sum hide-and-seek game whose value is called the search value of the network. We make a new and direct derivation of an explicit formula for the search...
-
作者：He, Simai; Jiang, Bo; Li, Zhening; Zhang, Shuzhong
作者单位：City University of Hong Kong; Shanghai University of Finance & Economics; University of Portsmouth; University of Minnesota System; University of Minnesota Twin Cities
摘要：Random sampling is a simple but powerful method in statistics and in the design of randomized algorithms. In a typical application, random sampling can be applied to estimate an extreme value, say maximum, of a function f over a set S subset of R-n. To do so, one may select a simpler (even finite) subset S-0 subset of S, randomly take some samples over S-0 for a number of times, and pick the best sample. The hope is to find a good approximate solution with reasonable chance. This paper sets ou...
-
作者：Hildebrand, Roland
摘要：On the interior of a regular convex cone K in n-dimensional real space there exist two canonical Hessian metrics, the one generated by the logarithm of the characteristic function, and the Cheng-Yau metric. The former is associated with a self-concordant logarithmically homogeneous barrier on K, the universal barrier. It is invariant with respect to the unimodular automorphism subgroup of K and is compatible with the operation of taking product cones, but in general it does not behave well und...
-
作者：Oliu-Barton, Miquel
作者单位：Universite Paris Cite; Centre National de la Recherche Scientifique (CNRS); CNRS - National Institute for Mathematical Sciences (INSMI); Sorbonne Universite
摘要：Bewley and Kohlberg [Bewley T, Kohlberg E (1976) The asymptotic theory of stochastic games. Math. Oper. Res. 1: 197-208] proved that the discounted values of finite zero-sum stochastic games have a limit, as the discount factor tends to zero, using the Tarski-Seidenberg elimination theorem from real algebraic geometry. This was a fundamental step in the development of the theory of stochastic games. The current paper provides a new and direct proof for this result, relying on the explicit desc...
-
作者：Hirai, Hiroshi
作者单位：University of Tokyo
摘要：We consider the weighted maximum multiflow problem with respect to a terminal weight. We show that if the dimension of the tight span associated with the weight is at most 2, then this problem has a 1/12-integral optimal multiflow for every Eulerian supply graph. This result solves a weighted generalization of Karzanov's conjecture for classifying commodity graphs with finite fractionality. In addition, our proof technique proves the existence of an integral or half-integrality optimal multifl...
-
作者：Adiprasito, Karim A.; Benedetti, Bruno
作者单位：Universite Paris Saclay
摘要：Using an intuition from metric geometry, we prove that any flag normal simplicial complex satisfies the nonrevisiting path conjecture. As a consequence, the diameter of its facet-ridge graph is smaller than the number of vertices minus the dimension, as in the Hirsch conjecture. This proves the Hirsch conjecture for all flag polytopes and, more generally, for all (connected) flag homology manifolds.
-
作者：Biswas, Anup
作者单位：Technion Israel Institute of Technology
摘要：A G/M/N queue is considered in the moderate deviation heavy traffic regime. The rate function for the customers-in-system process is obtained for the single class model. A risk-sensitive type control problem is considered for multiclass G/M/N model under the moderate deviation scaling and shown that the optimal control problem is related to a differential game problem.
-
作者：Ge, Dongdong; Wan, Guohua; Wang, Zizhuo; Zhang, Jiawei
作者单位：Shanghai University of Finance & Economics; Shanghai Jiao Tong University; University of Minnesota System; University of Minnesota Twin Cities; New York University
摘要：We consider the problem of determining the optimal schedules for a given sequence of jobs on a single processor. The objective is to minimize the expected total cost incurred by job waiting and processor idling, where the job processing times are random variables. It is known in the prior literature that if the processing times are integers and the costs are linear functions satisfying a mild condition, then the problem can be solved in a polynomial number of expected cost evaluations. In this...
-
作者：Olver, Neil; Shepherd, F. Bruce
作者单位：Massachusetts Institute of Technology (MIT); McGill University
摘要：We consider robust (undirected) network design (RND) problems where the set of feasible demands may be given by an arbitrary convex body. This model, introduced by Ben-Ameur and Kerivin [ Ben-Ameur W, Kerivin H (2003) New economical virtual private networks. Comm. ACM 46(6):69-73], generalizes the well-studied virtual private network (VPN) problem. Most research in this area has focused on constant factor approximations for specific polytope of demands, such as the class of hose matrices used ...
