-
作者：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...
-
作者：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...
-
作者：Bertsimas, Dimitris; Goyal, Vineet; Sun, Xu Andy
作者单位：Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT); Columbia University
摘要：In this paper, we show a significant role that geometric properties of uncertainty sets, such as symmetry, play in determining the power of robust and finitely adaptable solutions in multistage stochastic and adaptive optimization problems. We consider a fairly general class of multistage mixed integer stochastic and adaptive optimization problems and propose a good approximate solution policy with performance guarantees that depend on the geometric properties of the uncertainty sets. In parti...
-
作者：Cavazos-Cadena, Rolando; Hernandez-Hernandez, Daniel
作者单位：CIMAT - Centro de Investigacion en Matematicas
摘要：This work concerns Markov decision processes with finite state space and compact action set. The performance of a control policy is measured by a risk-sensitive average cost criterion and, under standard continuity-compactness conditions, it is shown that the discounted approximations converge to the optimal value function, and that the superior and inferior limit average criteria have the same optimal value function. These conclusions are obtained for every nonnull risk-sensitivity coefficien...
-
作者：Wachs, Allise O.; Schochetman, Irwin E.; Smith, Robert L.
作者单位：Oakland University; University of Michigan System; University of Michigan
摘要：We consider a nonhomogeneous stochastic infinite horizon optimization problem whose objective is to minimize the overall average cost per period of an infinite sequence of actions (average optimality). Optimal solutions to such problems will in general be nonstationary. Moreover, a solution that initially makes poor decisions, and then selects wisely thereafter, can be average optimal. However, we seek average optimal solutions with optimal short-term, as well as long-term, behavior. Our appro...
-
作者：Schulz, Andreas S.; Uhan, Nelson A.
作者单位：Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT); Purdue University System; Purdue University
摘要：We consider the problem of minimizing the weighted sum of completion times on a single machine subject to bipartite precedence constraints in which all minimal jobs have unit processing time and zero weight, and all maximal jobs have zero processing time and unit weight. For various probability distributions over these instances-including the uniform distribution-we show several almost all-type results. First, we show that almost all instances are prime with respect to a well-studied decomposi...
-
作者：Bolte, Jerome; Daniilidis, Aris; Lewis, Adrian S.
作者单位：Universite de Toulouse; Universite Toulouse 1 Capitole; Toulouse School of Economics; Autonomous University of Barcelona; Cornell University
摘要：We consider linear optimization over a nonempty convex semialgebraic feasible region F. Semidefinite programming is an example. If F is compact, then for almost every linear objective there is a unique optimal solution, lying on a unique active manifold, around which F is partly smooth, and the second-order sufficient conditions hold. Perturbing the objective results in smooth variation of the optimal solution. The active manifold consists, locally, of these perturbed optimal solutions; it is ...
