-
作者：Saban, Daniela; Sethuraman, Jay
作者单位：Columbia University; Columbia University
摘要：The random priority (RP) mechanism is a popular way to allocate n objects to n agents with strict ordinal preferences over the objects. In the RP mechanism, an ordering over the agents is selected uniformly at random; the first agent is then allocated his most-preferred object, the second agent is allocated his most-preferred object among the remaining ones, and so on. The outcome of the mechanism is a bi-stochastic matrix in which entry (i, a) represents the probability that agent i is given ...
-
作者：Jevtic, Petar; Steele, J. Michael
作者单位：McMaster University; University of Pennsylvania
摘要：A caterpillar network (or graph) G is a tree with the property that removal of the leaf edges of G leaves one with a path. Here we focus on minimum weight spanning caterpillars where the vertices are points in the Euclidean plane and the costs of the path edges and the leaf edges are multiples of their corresponding Euclidean lengths. The flexibility in choosing the weight for path edges versus the weight for leaf edges gives some useful flexibility in modeling. In particular, one can accommod...
-
作者：Mastrogiacomo, Elisa; Gianin, Emanuela Rosazza
作者单位：University of Milano-Bicocca
摘要：In this paper, we focus on the portfolio optimization problem associated with a quasiconvex risk measure (satisfying some additional assumptions). For coherent/convex risk measures, the portfolio optimization problem has been already studied in the literature. Following the approach of Ruszczynski and Shapiro [Ruszczynski A, Shapiro A (2006) Optimization of convex risk functions. Math. Oper. Res. 31(3): 433-452.], but by means of quasiconvex analysis and notions of subdifferentiability, we cha...
-
作者：Post, Ian; Ye, Yinyu
作者单位：University of Waterloo; Stanford University
摘要：We prove that the simplex method with the highest gain/most-negative-reduced cost pivoting rule converges in strongly polynomial time for deterministic Markov decision processes (MDPs) regardless of the discount factor. For a deterministic MDP with n states and m actions, we prove the simplex method runs in O(n(3) m(2) log(2) n) iterations if the discount factor is uniform and O(n(5) m(3) log(2) n) iterations if each action has a distinct discount factor. Previously the simplex method was know...
-
作者：Sumita, Hanna; Kakimura, Naonori; Makino, Kazuhisa
作者单位：University of Tokyo; University of Tokyo; Kyoto University
摘要：In this paper, we consider the sparse linear complementarity problem, denoted by k-LCP: the coefficient matrices are restricted to have at most k nonzero entries per row. It is known that the 1-LCP is solvable in linear time, and the 3-LCP is strongly NP-hard. We show that the 2-LCP is strongly NP-hard, and it can be solved in polynomial time if it is sign-balanced, i. e., each row of the matrix has at most one positive and one negative entry. Our second result matches the currently best-known...
-
作者：Defourny, Boris; Ryzhov, Ilya O.; Powell, Warren B.
作者单位：Lehigh University; University System of Maryland; University of Maryland College Park; Princeton University
摘要：A sequential information collection problem, where a risk-averse decision maker updates a Bayesian belief about the unknown objective function of a linear program, is used to investigate the informational value of measurements performed to refine a robust optimization model. The information is collected in the form of a linear combination of the objective coefficients, subject to random noise. We have the ability to choose the weights in the linear combination, creating a new, nonconvex contin...
