-
作者：Akan, Mustafa; Ata, Baris
作者单位：Carnegie Mellon University; Northwestern University
摘要：We consider a continuous-time, rate-based model of network revenue management. Under mild assumptions, we construct a simple epsilon- optimal bid-price control, which can be viewed as a perturbation of a bid-price control in the classical sense [Williamson, E. L. 1992. Airline network seat control. Ph.D. thesis, MIT, Cambridge, MA]. We show that the associated bid-price process forms a martingale and the corresponding booking controls converge in an appropriate sense to an optimal control as e...
-
作者：Nagarajan, Viswanath; Sviridenko, Maxim
作者单位：International Business Machines (IBM); IBM USA
摘要：Quadratic assignment is a basic problem in combinatorial optimization that generalizes several other problems such as traveling salesman, linear arrangement, dense k subgraph, and clustering with given sizes. The input to the quadratic assignment problem consists of two n x n symmetric nonnegative matrices W = (w(i,j)) and D = (d(i,j)). Given matrices W, D, and a permutation pi: [n] -> [n], the objective function is Q(pi) := Sigma(i,j is an element of[n], i not equal j) w(i,j) . d(pi(i), pi(j)...
-
作者：Cardaliaguet, Pierre; Rainer, Catherine
作者单位：Centre National de la Recherche Scientifique (CNRS); CNRS - National Institute for Mathematical Sciences (INSMI); Universite de Bretagne Occidentale
摘要：For zero-sum two-player continuous-time games with integral payoff and incomplete information on one side, the authors show that the optimal strategy of the informed player can be computed through an auxiliary optimization problem over some martingale measures. The authors also characterize the optimal martingale measures and compute them explicitly in several examples.
-
作者：Ding, Yichuan; Wolkowicz, Henry
作者单位：Stanford University; University of Waterloo
摘要：The quadratic assignment problem (QAP) is arguably one of the hardest NP-hard discrete optimization problems. Problems of dimension greater than 25 are still considered to be large scale. Current successful solution techniques use branch-and-bound methods, which rely on obtaining strong and inexpensive bounds. In this paper, we introduce a new semidefinite programming (SDP) relaxation for generating bounds for the QAP in the trace formulation. We apply majorization to obtain a relaxation of th...
-
作者：Galluccio, Anna; Gentile, Claudio; Ventura, Paolo
作者单位：Consiglio Nazionale delle Ricerche (CNR)
摘要：Graphs obtained by applying the gear composition to a given graph H are called geared graphs. We show how a linear description of the stable set polytope STAB(G) of a geared graph G can be obtained by extending the linear inequalities defining STAB (H) and STAB (H-e), where He is the graph obtained from H by subdividing the edge e. We also introduce the class of G-perfect graphs, i.e., graphs whose stable set polytope is described by nonnegativity inequalities, rank inequalities, lifted 5-whee...
-
作者：Zadorojniy, Alexander; Even, Guy; Shwartz, Adam
作者单位：Tel Aviv University; Technion Israel Institute of Technology
摘要：We consider the problem of computing optimal policies of finite-state finite-action Markov decision processes (MDPs). A reduction to a continuum of constrained MDPs (CMDPs) is presented such that the optimal policies for these CMDPs constitute a path in a graph defined over the deterministic policies. This path contains, in particular, an optimal policy of the original MDP. We present an algorithm based on this new approach that finds this path, and thus an optimal policy. In the general case,...
-
作者：Blanquero, Rafael; Carrizosa, Emilio; Hansen, Pierre
作者单位：University of Sevilla; Universite de Montreal; Universite de Montreal; HEC Montreal
摘要：We address the problem of locating objects in the plane such as segments, arcs of circumferences, arbitrary convex sets, their complements or their boundaries. Given a set of points, we seek the rotation and translation for such an object optimizing a very general performance measure, which includes as a particular case the classical objectives in semi-obnoxious facility location. In general, the above-mentioned model yields a global optimization problem, whose resolution is dealt with using d...
-
作者：Freund, Robert M.; Vera, Jorge R.
作者单位：Massachusetts Institute of Technology (MIT); Pontificia Universidad Catolica de Chile
摘要：Consider the supposedly simple problem of computing a point in a convex set that is conveyed by a separation oracle with no further information (e. g., no domain ball containing or intersecting the set, etc.). The authors' interest in this problem stems from fundamental issues involving the interplay of (i) the computational complexity of computing a point in the set, (ii) the geometry of the set, and (iii) the stability or conditioning of the set under perturbation. Under suitable definitions...
-
作者：Kern, Walter; Paulusma, Daniel
作者单位：University of Twente; Durham University
摘要：Using the ellipsoid method, both Deng et al. [Deng, X., Q. Fang, X. Sun. 2006. Finding nucleolus of flow game. Proc. 17th ACM-SIAM Sympos. Discrete Algorithms. ACM Press, New York, 124-131] and Potters et al. [Potters, J., H. Reijnierse, A. Biswas. 2006. The nucleolus of balanced simple flow networks. Games Econom. Behav. 54 205-225] show that the nucleolus of simple flow games (where all edge capacities are equal to one) can be computed in polynomial time. Our main result is a combinatorial m...
-
作者：Zhang, Jiheng; Dai, J. G.; Zwart, Bert
作者单位：University System of Georgia; Georgia Institute of Technology
摘要：Motivated by applications in computer and communication systems, we consider a processor-sharing queue where the number of jobs served is not larger than K. We propose a measure-valued fluid model for this limited processor-sharing queue and show that there exists a unique associated fluid model solution. In addition, we show that this fluid model arises as the limit of a sequence of appropriately scaled processor-sharing queues.
