作者：Teo, CP; Sethuraman, J
作者单位：National University of Singapore; Massachusetts Institute of Technology (MIT)
摘要：We study the classical stable marriage and stable roommates problems using a polyhedral approach. We propose a new LP formulation for the stable roommates problem, which has a feasible solution if and only if the underlying roommates problem has a stable matching. Furthermore, for certain special weight functions on the edges, we construct a a-approximation algorithm for the optimal stable roommates problem. Our technique exploits features of the geometry of fractional solutions of this formul...
作者：Bonnans, JF; Cominetti, R; Shapiro, A
作者单位：Universidad de Chile; University System of Georgia; Georgia Institute of Technology
摘要：We present a perturbation theory for finite dimensional optimization problems subject to abstract constraints satisfying a second order regularity condition. This is a technical condition that is always satisfied in the case of semi-definite optimization. We derive Lipschitz and Holder expansions of approximate optimal solutions, under a directional constraint qualification hypothesis and various second order sufficient conditions that take into account the curvature of the set defining the co...
