-
作者：Kindler, Guy; Naor, Assaf; Schechtman, Gideon
作者单位：Hebrew University of Jerusalem; New York University; Weizmann Institute of Science
摘要：For p >= 2 we consider the problem of, given an n x n matrix A = (a(ij)) whose diagonal entries vanish, approximating in polynomial time the number Opt(p)(A):= max{(i,j=1)Sigma(n) a(ij)x(i)x(j): (x(1), ..., x(n)) is an element of R-n boolean AND ((i=1)Sigma(n) vertical bar x(i)vertical bar(p))(1/p) <= 1}. When p = 2 this is simply the problem of computing the maximum eigenvalue of A, whereas for p = infinity ( actually it suffices to take p approximate to log n) it is the Grothendieck problem ...
-
作者：Bonifaci, Vincenzo; Harks, Tobias; Schafer, Guido
作者单位：Max Planck Society; Technical University of Berlin
摘要：We investigate the impact of Stackelberg routing to reduce the price of anarchy in network routing games. In this setting, an alpha fraction of the entire demand is first routed centrally according to a predefined Stackelberg strategy and the remaining demand is then routed selfishly by (nonatomic) players. Although several advances have been made recently in proving that Stackelberg routing can, in fact, significantly reduce the price of anarchy for certain network topologies, the central que...
-
作者：Bertsimas, Dimitris; Goyal, Vineet
作者单位：Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT)
摘要：We consider a two-stage mixed integer stochastic optimization problem and show that a static robust solution is a good approximation to the fully adaptable two-stage solution for the stochastic problem under fairly general assumptions on the uncertainty set and the probability distribution. In particular, we show that if the right-hand side of the constraints is uncertain and belongs to a symmetric uncertainty set (such as hypercube, ellipsoid or norm ball) and the probability measure is also ...
-
作者：Rusmevichientong, Paat; Tsitsiklis, John N.
作者单位：Cornell University; Massachusetts Institute of Technology (MIT)
摘要：We consider bandit problems involving a large (possibly infinite) collection of arms, in which the expected reward of each arm is a linear function of an r-dimensional random vector Z is an element of R-r, where r >= 2. The objective is to minimize the cumulative regret and Bayes risk. When the set of arms corresponds to the unit sphere, we prove that the regret and Bayes risk is of order Theta(r root T), by establishing a lower bound for an arbitrary policy, and showing that a matching upper ...
-
作者：Yu, Huizhen; Bertsekas, Dimitri P.
作者单位：University of Helsinki; Massachusetts Institute of Technology (MIT)
摘要：We consider linear fixed point equations and their approximations by projection on a low dimensional subspace. We derive new bounds on the approximation error of the solution, which are expressed in terms of low dimensional matrices and can be computed by simulation. When the fixed point mapping is a contraction, as is typically the case in Markov decision processes (MDP), one of our bounds is always sharper than the standard contraction-based bounds, and another one is often sharper. The form...
-
作者：Vazirani, Vijay V.
作者单位：University System of Georgia; Georgia Institute of Technology
摘要：The notion of a market has undergone a paradigm shift with the Internet. Totally new and highly successful markets have been defined and launched by Internet companies, which already form an important part of today's economy and are projected to grow considerably in the future. Another major change is the availability of massive computational power for running these markets in a centralized or distributed manner. In view of these new realities, the study of market equilibria, an important, tho...
-
作者：Hoda, Samid; Gilpin, Andrew; Pena, Javier; Sandholm, Tuomas
作者单位：Carnegie Mellon University; Carnegie Mellon University
摘要：We develop first-order smoothing techniques for saddle-point problems that arise in finding a Nash equilibrium of sequential games. The crux of our work is a construction of suitable prox-functions for a certain class of polytopes that encode the sequential nature of the game. We also introduce heuristics that significantly speed up the algorithm, and decomposed game representations that reduce the memory requirements, enabling the application of the techniques to drastically larger games. An ...
-
作者：Cook, William J.; Espinoza, Daniel G.; Goycoolea, Marcos
作者单位：University System of Georgia; Georgia Institute of Technology; Universidad de Chile; Universidad Adolfo Ibanez
摘要：We extend the work of Letchford [Letchford, A. N. 2000. Separating a superclass of comb inequalities in planar graphs. Math. Oper. Res. 25 443-454] by introducing a new class of valid inequalities for the traveling salesman problem, called the generalized domino-parity (GDP) constraints. Just as Letchford's domino-parity constraints generalize comb inequalities, GDP constraints generalize the most well-known multiple-handle constraints, including clique-tree, bipartition, path, and star inequa...
-
作者：Dieker, A. B.; Warren, J.
作者单位：University System of Georgia; Georgia Institute of Technology; University of Warwick
摘要：This paper studies the queue-length process in series Jackson networks with external input to the first station only. We show that its Markov transition probabilities can be written as a finite sum of noncrossing probabilities, so that questions on time-dependent queueing behavior are translated to questions on noncrossing probabilities. This makes previous work on noncrossing probabilities relevant to queueing systems and allows new queueing results to be established. To illustrate the latter...
-
作者：Bertsimas, Dimitris; Iancu, Dan A.; Parrilo, Pablo A.
作者单位：Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT)
摘要：In this paper, we prove the optimality of disturbance-affine control policies in the context of one-dimensional, constrained, multistage robust optimization. Our results cover the finite-horizon case, with minimax (worst-case) objective, and convex state costs plus linear control costs. We develop a new proof methodology, which explores the relationship between the geometrical properties of the feasible set of solutions and the structure of the objective function. Apart from providing an elega...
