-
作者：Frieze, A
作者单位：Carnegie Mellon University
摘要：Let the edges of the complete graph K-n be assigned independent uniform [0, 1] random edge weights. Let Z(TSP) and Z(2FAC) be the weights of the minimum length travelling salesman tour and minimum weight 2-factor, respectively. We show that whp \Z(TSP) - Z(2FAC)\ = o(1). The proof is obtained by the analysis of a polynomial time algorithm that finds a tour only a little longer than Z(2FAC).
-
作者：Ben-Ameur, H; L'Ecuyer, P; Lemieux, C
作者单位：Universite de Montreal; HEC Montreal; Universite de Montreal; HEC Montreal; Universite de Montreal; Universite de Montreal; University of Calgary
摘要：Several methods for reducing the variance in the context of Monte Carlo simulation are based on correlation induction. This includes antithetic variates, Latin hypercube sampling, and randomized version of quasi-Monte Carlo methods such as lattice rules and digital nets. where the resulting estimators are usually weighted averages of several dependent random variables that can be seen as function evaluations at a finite set of random points in the unit hypercube. In this paper. we consider a s...
-
作者：Powell, W; Ruszczynski, A; Topaloglu, H
作者单位：Princeton University; Rutgers University System; Rutgers University New Brunswick; Cornell University
摘要：We propose the use of sequences of separable, piecewise linear approximations for solving nondifferentiable stochastic optimization problems. The approximations are constructed adaptively using a combination of stochastic subgradient information and possibly sample information on the objective function itself. We prove the convergence of several versions of such methods when the objective function is separable and has integer break points, and we illustrate their behavior on numerical examples...
-
作者：Neyman, A; Smorodinsky, R
作者单位：Hebrew University of Jerusalem; Hebrew University of Jerusalem; Technion Israel Institute of Technology
摘要：The asymptotic value, introduced by Kannai in 1966, is an asymptotic approach to the notion of the Shapley value for games with infinitely many players. A vector measure game is a game v where the worth v(S) of a coalition S is a function f of mu(S) where mu is a vector measure. Special classes of vector measure games are the weighted majority games and the two-house weighted majority games, where a two-house weighted majority game is a game in which a coalition is winning if and only if it is...
-
作者：Correa, JR; Schulz, AS; Stier-Moses, NE
作者单位：Universidad de Chile; Massachusetts Institute of Technology (MIT); Columbia University
摘要：According to Wardrop's first principle, agents in a congested network choose their routes selfishly, a behavior that is captured by the Nash equilibrium of the underlying noncooperative game. A Nash equilibrium does not optimize any global criterion per se, and so there is no apparent reason why it should be close to a solution of minimal total travel time, i.e., the system optimum. In this paper, we offer positive results on the efficiency of Nash equilibria in traffic networks. In contrast t...
-
作者：Dai, JG; Jennings, OB
作者单位：University System of Georgia; Georgia Institute of Technology; Duke University
摘要：For multiclass queueing networks, dispatch policies govern the assignment of servers to the jobs they process. Production policies perform the analogous task for queueing networks whose servers are subject to switch-over delays or setups, a model we refer to as setup networks. It is well known that a poorly chosen dispatch policy may lead to instability of a multiclass queueing network, even when the traffic intensity at each station is less than one and the policy is nonidling. Not surprising...
-
作者：Maglaras, C; Zeevi, A
作者单位：Columbia University
摘要：This paper considers a Markovian model of a service system motivated by communication and information services. The system has finite processing capacity and offers multiple grades of service. The highest priority users receive a guaranteed processing rate, while lower priority users share residual capacity according to their priority level and therefore may experience service degradation (hence the term best effort). This paper focuses on performance analysis for this class of systems. We con...
