-
作者：Goel, Gagan; Vazirani, Vijay V.
作者单位：Alphabet Inc.; Google Incorporated; University System of Georgia; Georgia Institute of Technology
摘要：Recent results showing PPAD-completeness of the problem of computing an equilibrium for Fisher's market model under additively separable, piecewise-linear, concave (PLC) utilities have dealt a serious blow to the program of obtaining efficient algorithms for computing equilibria in traditional market models, and has prompted a search for alternative models that are realistic as well as amenable to efficient computation. In this paper, we show that introducing perfect price discrimination into ...
-
作者：Ashlagi, Itai; Monderer, Dov; Tennenholtz, Moshe
作者单位：Massachusetts Institute of Technology (MIT); Technion Israel Institute of Technology; Microsoft; MICROSOFT ISRAEL
摘要：We consider a model with two simultaneous VCG ad auctions A and B where each advertiser chooses to participate in a single ad auction. We prove the existence and uniqueness of a symmetric equilibrium in that model. Moreover, when the click rates in A are pointwise higher than those in B, we prove that the expected revenue in A is greater than the expected revenue in B in this equilibrium. In contrast, we show that this revenue ranking does not hold when advertisers can participate in both auct...
-
作者：Kruk, Lukasz
作者单位：Maria Curie-Sklodowska University
摘要：We provide an example of a feedforward first-in-system, first-out (FISFO) queueing network with unconventional, i.e., non-Brownian, heavy traffic diffusion approximation. We also prove that fluid models of subcritical feedforward earliest-deadline-first (EDF) queueing networks are asymptotically stable.
-
作者：Ye, Yinyu
作者单位：Stanford University
摘要：We prove that the classic policy-iteration method [Howard, R. A. 1960. Dynamic Programming and Markov Processes. MIT, Cambridge] and the original simplex method with the most-negative-reduced-cost pivoting rule of Dantzig are strongly polynomial-time algorithms for solving the Markov decision problem (MDP) with a fixed discount rate. Furthermore, the computational complexity of the policy-iteration and simplex methods is superior to that of the only known strongly polynomial-time interior-poin...
-
作者：Begen, Mehmet A.; Queyranne, Maurice
作者单位：Western University (University of Western Ontario); University of British Columbia
摘要：We consider the problem of determining an optimal appointment schedule for a given sequence of jobs (e. g., medical procedures) on a single processor (e. g., operating room, examination facility, physician), to minimize the expected total underage and overage costs when each job has a random processing duration given by a joint discrete probability distribution. Simple conditions on the cost rates imply that the objective function is submodular and L-convex. Then there exists an optimal appoin...
-
作者：Antonakopoulos, Spyridon; Chekuri, Chandra; Shepherd, Bruce; Zhang, Lisa
作者单位：Alcatel-Lucent; AT&T; University of Illinois System; University of Illinois Urbana-Champaign; McGill University
摘要：We consider approximation algorithms for buy-at-bulk network design, with the additional constraint that demand pairs be protected against a single edge or node failure in the network. In practice, the most popular model used in high-speed telecommunication networks for protection against failures is the so-called 1 + 1 model. In this model, two-edge or node-disjoint paths are provisioned for each demand pair. We obtain the first nontrivial approximation algorithms for buy-at-bulk network desi...
-
作者：Guo, Xianping; Piunovskiy, Alexei
作者单位：Sun Yat Sen University; University of Liverpool
摘要：This paper deals with denumerable continuous-time Markov decision processes (MDP) with constraints. The optimality criterion to be minimized is expected discounted loss, while several constraints of the same type are imposed. The transition rates may be unbounded, the loss rates are allowed to be unbounded as well (from above and from below), and the policies may be history-dependent and randomized. Based on Kolmogorov's forward equation and Dynkin's formula, we remind the reader about the Bel...
-
作者：Ding, Yichuan; Ge, Dongdong; Wolkowicz, Henry
作者单位：Stanford University; Shanghai Jiao Tong University; University of Waterloo
摘要：We analyze two popular semidefinite programming relaxations for quadratically constrained quadratic programs with matrix variables. These relaxations are based on vector lifting and on matrix lifting; they are of different size and expense. We prove, under mild assumptions, that these two relaxations provide equivalent bounds. Thus, our results provide a theoretical guideline for how to choose a less expensive semidefinite programming relaxation and still obtain a strong bound. The main techni...
-
作者：Liu, Yongchao; Xu, Huifu; Ye, Jane J.
作者单位：Dalian Maritime University; University of Southampton; University of Victoria
摘要：This paper considers a one-stage stochastic mathematical program with a complementarity constraint (SMPCC), where uncertainties appear in both the objective function and the complementarity constraint, and an optimal decision on both upper- and lower-level decision variables must be made before the realization of the uncertainties. A partially exactly penalized sample average approximation (SAA) scheme is proposed to solve the problem. Asymptotic convergence of optimal solutions and stationary...
-
作者：Dey, Santanu S.; Louveaux, Quentin
作者单位：University System of Georgia; Georgia Institute of Technology; University of Liege
摘要：A simple relaxation consisting of two rows of a simplex tableau is a mixed-integer set with two equations, two free integer variables, and nonnegative continuous variables. Recently, Andersen et al. and Cornuejols and Margot showed that the facet-defining inequalities of this set are either split cuts or intersection cuts obtained from lattice-free triangles and quadrilaterals. From an example given by Cook et al. it is known that one particular class of facet-defining triangle inequality does...
