2011

最新文章

• Budgeted matching and budgeted matroid intersection via the gasoline puzzle AI翻译
  作者：Berger, Andre; Bonifaci, Vincenzo; Grandoni, Fabrizio; Schafer, Guido
  作者单位：Sapienza University Rome; Maastricht University; University of L'Aquila; University of Rome Tor Vergata; Centrum Wiskunde & Informatica (CWI); Vrije Universiteit Amsterdam
  摘要：Many polynomial-time solvable combinatorial optimization problems become NP-hard if an additional complicating constraint is added to restrict the set of feasible solutions. In this paper, we consider two such problems, namely maximum-weight matching and maximum-weight matroid intersection with one additional budget constraint. We present the first polynomial-time approximation schemes for these problems. Similarly to other approaches for related problems, our schemes compute two solutions to ...
• Implications of the constant rank constraint qualification AI翻译
  作者：Lu, Shu
  作者单位：University of North Carolina; University of North Carolina Chapel Hill
  摘要：This paper investigates properties of a parametric set defined by finitely many equality and inequality constraints under the constant rank constraint qualification (CRCQ). We show, under the CRCQ, that the indicator function of this set is prox-regular with compatible parametrization, that the set-valued map that assigns each parameter to the set defined by that parameter satisfies a continuity property similar to the Aubin property, and that the Euclidean projector onto this set is a piecewi...
• Branching on general disjunctions AI翻译
  作者：Karamanov, Miroslav; Cornuejols, Gerard
  作者单位：Carnegie Mellon University
  摘要：This paper considers a modification of the branch-and-cut algorithm for Mixed Integer Linear Programming where branching is performed on general disjunctions rather than on variables. We select promising branching disjunctions based on a heuristic measure of disjunction quality. This measure exploits the relation between branching disjunctions and intersection cuts. In this work, we focus on disjunctions defining the mixed integer Gomory cuts at an optimal basis of the linear programming relax...
• Statistical ranking and combinatorial Hodge theory AI翻译
  作者：Jiang, Xiaoye; Lim, Lek-Heng; Yao, Yuan; Ye, Yinyu
  作者单位：University of California System; University of California Berkeley; Stanford University; Peking University; Peking University; Stanford University
  摘要：We propose a technique that we call HodgeRank for ranking data that may be incomplete and imbalanced, characteristics common in modern datasets coming from e-commerce and internet applications. We are primarily interested in cardinal data based on scores or ratings though our methods also give specific insights on ordinal data. From raw ranking data, we construct pairwise rankings, represented as edge flows on an appropriate graph. Our statistical ranking method exploits the graph Helmholtzian...
• Bilinear optimality constraints for the cone of positive polynomials AI翻译
  作者：Rudolf, Gabor; Noyan, Nilay; Papp, David; Alizadeh, Farid
  作者单位：Virginia Commonwealth University; Sabanci University; Northwestern University; Rutgers University System; Rutgers University New Brunswick; Rutgers University System; Rutgers University New Brunswick
  摘要：For a proper cone K subset of R-n and its dual cone K* the complementary slackness condition < x, s > = 0 defines an n-dimensional manifold C(K) in the space R-2n. When K is a symmetric cone, points in C(K) must satisfy at least n linearly independent bilinear identities. This fact proves to be useful when optimizing over such cones, therefore it is natural to look for similar bilinear relations for non-symmetric cones. In this paper we define the bilinearity rank of a cone, which is the numbe...
• Strong KKT conditions and weak sharp solutions in convex-composite optimization AI翻译
  作者：Zheng, Xi Yin; Ng, Kung Fu
  作者单位：Yunnan University; Chinese University of Hong Kong
  摘要：Using variational analysis techniques, we study convex-composite optimization problems. In connection with such a problem, we introduce several new notions as variances of the classical KKT conditions. These notions are shown to be closely related to the notions of sharp or weak sharp solutions. As applications, we extend some results on metric regularity of inequalities from the convex case to the convex-composite case.
• Primal-dual first-order methods with O(1/ε) iteration-complexity for cone programming AI翻译
  作者：Lan, Guanghui; Lu, Zhaosong; Monteiro, Renato D. C.
  作者单位：University System of Georgia; Georgia Institute of Technology; Simon Fraser University; University System of Georgia; Georgia Institute of Technology
  摘要：In this paper we consider the general cone programming problem, and propose primal-dual convex (smooth and/or nonsmooth) minimization reformulations for it. We then discuss first-order methods suitable for solving these reformulations, namely, Nesterov's optimal method (Nesterov in Doklady AN SSSR 269:543-547, 1983; Math Program 103:127-152, 2005), Nesterov's smooth approximation scheme (Nesterov in Math Program 103: 127-152, 2005), and Nemirovski's prox-method (Nemirovski in SIAM J Opt 15: 22...
• A stackelberg game approach to distributed spectrum management AI翻译
  作者：Razaviyayn, Meisam; Luo, Zhi-Quan; Tseng, Paul; Pang, Jong-Shi
  作者单位：University of Minnesota System; University of Minnesota Twin Cities; University of Washington; University of Washington Seattle; University of Illinois System; University of Illinois Urbana-Champaign
  摘要：We consider a cognitive radio system with one primary (licensed) user and multiple secondary (unlicensed) users. Given the interference temperature constraint, the secondary users compete for the available spectrum to fulfill their own communication need. Borrowing the concept of price from market theory, we develop a decentralized Stackelberg game formulation for power allocation. In this scheme, the primary user (leader) announces prices for the available tones such that a system utility is ...
• A warm-start approach for large-scale stochastic linear programs AI翻译
  作者：Colombo, Marco; Gondzio, Jacek; Grothey, Andreas
  作者单位：University of Edinburgh; Heriot Watt University
  摘要：We describe a way of generating a warm-start point for interior point methods in the context of stochastic programming. Our approach exploits the structural information of the stochastic problem so that it can be seen as a structure-exploiting initial point generator. We solve a small-scale version of the problem corresponding to a reduced event tree and use the solution to generate an advanced starting point for the complete problem. The way we produce a reduced tree tries to capture the impo...
• A class of nonlinear nonseparable continuous knapsack and multiple-choice knapsack problems AI翻译
  作者：Sharkey, Thomas C.; Romeijn, H. Edwin; Geunes, Joseph
  作者单位：Rensselaer Polytechnic Institute; University of Michigan System; University of Michigan; State University System of Florida; University of Florida
  摘要：This paper considers a general class of continuous, nonlinear, and nonseparable knapsack problems, special cases of which arise in numerous operations and financial contexts. We develop important properties of optimal solutions for this problem class, based on the properties of a closely related class of linear programs. Using these properties, we provide a solution method that runs in polynomial time in the number of decision variables, while also depending on the time required to solve a par...