-
作者：Navidi, Fatemeh; Kambadur, Prabhanjan; Nagarajan, Viswanath
作者单位：University of Michigan System; University of Michigan; Bloomberg L.P.
摘要：We study a general stochastic ranking problem in which an algorithm needs to adaptively select a sequence of elements so as to cover a random scenario (drawn from a known distribution) at minimum expected cost. The coverage of each scenario is captured by an individual submodular function, in which the scenario is said to be covered when its function value goes above a given threshold. We obtain a logarithmic factor approximation algorithm for this adaptive ranking problem, which is the best p...
-
作者：Rahmaniani, Ragheb; Ahmed, Shabbir; Crainic, Teodor Gabriel; Gendreau, Michel; Rei, Walter
作者单位：University System of Georgia; Georgia Institute of Technology; University of Quebec; University of Quebec Montreal; Universite de Montreal; University of Quebec; University of Quebec Montreal; Universite de Montreal; Polytechnique Montreal; Universite de Montreal; Polytechnique Montreal
摘要：Many methods that have been proposed to solve large-scale mixed integer linear programing (MILP) problems rely on decomposition techniques. These methods exploit either the primal or the dual structure of the problem, yielding the Benders decomposition or Lagrangian dual decomposition methods. We propose a new and high-performance approach, called Benders dual decomposition (BDD), which combines the complementary advantages of both methods. The development of BDD is based on a specific reformu...
-
作者：Johnson, David S.; Breslau, Lee; Diakonikolas, Ilias; Duffield, Nick; Gu, Yu; Hajiaghayi, MohammadTaghi; Karloff, Howard; Resende, Mauricio G. C.; Sen, Subhabrata
作者单位：AT&T; University of Wisconsin System; University of Wisconsin Madison; Texas A&M University System; Texas A&M University College Station; Amazon.com; University System of Maryland; University of Maryland College Park; Amazon.com; University of Washington; University of Washington Seattle; Nokia Corporation; Nokia Bell Labs; AT&T
摘要：In this paper, we consider two special cases of the cover-by-pairs optimization problem that arises when we need to place facilities so that each customer is served by two facilities that reach it by disjoint shortest paths. These problems arise in a network trafficmonitoring scheme proposed by Breslau et al. and have potential applications to content distribution. The set-disjoint variant applies to networks that use the open shortest path first routing protocol, and the path-disjoint variant...
-
作者：Zorc, Sasa; Tsetlin, Ilia
作者单位：University of Virginia; INSEAD Business School
摘要：We model two agents who can benefit from a mutual deal or partnership, yet are also searching for outside alternatives. This generic situation is observed in various settings (e.g., the job market for experts) and involves several decisions. The proposer decides not only on the timing, deadline, and value of her offer but also on how to handle her outside alternatives; the responder decides whether to accept the proposer's offer (if any) and how to handle his own outside alternatives. A respon...
-
作者：Bertsimas, Dimitris; Sturt, Bradley
作者单位：Massachusetts Institute of Technology (MIT)
摘要：The bootstrap is a nonparametric approach for calculating quantities, such as confidence intervals, directly from data. Since calculating exact bootstrap quantities is believed to be intractable, randomized resampling algorithms are traditionally used. In this paper, we present a new perspective on the bootstrapmethod through the lens of counting integer points in polyhedra. Through this new perspective, we make several advances for the bootstrap method, both theoretically and algorithmically....
-
作者：Ma, Yuhang; Rusmevichientong, Paat; Sumida, Mika; Topaloglu, Huseyin
作者单位：University of Southern California
摘要：We provide an approximation algorithm for network revenue management problems. In our approximation algorithm, we construct an approximate policy using value function approximations that are expressed as linear combinations of basis functions. We use a backward recursion to compute the coefficients of the basis functions in the linear combinations. If each product uses at most L resources, then the total expected revenue obtained by our approximate policy is at least 1/(1 + L) of the optimal t...
