2017

最新文章

• Stochastic second-order-cone complementarity problems: expected residual minimization formulation and its applications AI翻译
  作者：Lin, Gui-Hua; Luo, Mei-Ju; Zhang, Dali; Zhang, Jin
  作者单位：Shanghai University; Liaoning University; Shanghai Jiao Tong University; Hong Kong Baptist University
  摘要：This paper considers a class of stochastic second-order-cone complementarity problems (SSOCCP), which are generalizations of the noticeable stochastic complementarity problems and can be regarded as the Karush-Kuhn-Tucker conditions of some stochastic second-order-cone programming problems. Due to the existence of random variables, the SSOCCP may not have a common solution for almost every realization . In this paper, motivated by the works on stochastic complementarity problems, we present a ...
• Hirsch polytopes with exponentially long combinatorial segments AI翻译
  作者：Labbe, Jean-Philippe; Manneville, Thibault; Santos, Francisco
  作者单位：Hebrew University of Jerusalem; Centre National de la Recherche Scientifique (CNRS); CNRS - Institute for Information Sciences & Technologies (INS2I); Institut Polytechnique de Paris; Ecole Polytechnique; Universidad de Cantabria
  摘要：In their paper proving the Hirsch bound for flag normal simplicial complexes, Adiprasito and Benedetti (Math Oper Res 39(4):1340-1348, 2014) define the notion of combinatorial segment. The study of the maximal length of these objects provides the upper bound for the diameter of any normal pure simplicial complex of dimension d with n vertices, and the Hirsch bound if the complexes are moreover flag. In the present article, we propose a formulation of combinatorial segments which is equivalent ...
• Integer round-up property for the chromatic number of some h-perfect graphs AI翻译
  作者：Benchetrit, Yohann
  作者单位：Communaute Universite Grenoble Alpes; Institut National Polytechnique de Grenoble; Universite Grenoble Alpes (UGA); Centre National de la Recherche Scientifique (CNRS); Communaute Universite Grenoble Alpes; Institut National Polytechnique de Grenoble; Universite Grenoble Alpes (UGA); Centre National de la Recherche Scientifique (CNRS)
  摘要：We prove that every h-perfect line graph and every t-perfect claw-free graph G has the integer round-up property for the chromatic number: for every non-negative integral weight function c on the vertices of G, the weighted chromatic number of (G, c) can be obtained by rounding up its fractional relaxation. As a corollary, we obtain that the weighted chromatic number can be computed in polynomial-time for these graphs. Finally, we show a new example of a graph operation which preserves the int...
• Polyhedral aspects of score equivalence in Bayesian network structure learning AI翻译
  作者：Cussens, James; Haws, David; Studeny, Milan
  作者单位：University of York - UK; University of York - UK; International Business Machines (IBM); IBM USA; Czech Academy of Sciences; Institute of Information Theory & Automation of the Czech Academy of Sciences
  摘要：This paper deals with faces and facets of the family-variable polytope and the characteristic-imset polytope, which are special polytopes used in integer linear programming approaches to statistically learn Bayesian network structure. A common form of linear objectives to be maximized in this area leads to the concept of score equivalence (SE), both for linear objectives and for faces of the family-variable polytope. We characterize the linear space of SE objectives and establish a one-to-one ...
• Convex optimization learning of faithful Euclidean distance representations in nonlinear dimensionality reduction AI翻译
  作者：Ding, Chao; Qi, Hou-Duo
  作者单位：Chinese Academy of Sciences; University of Southampton
  摘要：Classical multidimensional scaling only works well when the noisy distances observed in a high dimensional space can be faithfully represented by Euclidean distances in a low dimensional space. Advanced models such as Maximum Variance Unfolding (MVU) and Minimum Volume Embedding (MVE) use Semi-Definite Programming (SDP) to reconstruct such faithful representations. While those SDP models are capable of producing high quality configuration numerically, they suffer two major drawbacks. One is th...
• Tight bounds on indefinite separable singly-constrained quadratic programs in linear-time AI翻译
  作者：Edirisinghe, Chanaka; Jeong, Jaehwan
  作者单位：Rensselaer Polytechnic Institute; Radford University
  摘要：Non-convex knapsack separable quadratic optimization with compact box constraints is an NP-hard problem. We present tight lower and upper bounding procedures that are computationally-efficient as the problem size grows. The lower bound is based on Lagrangian relaxation, and it is computed in linear-time. When the bound is not an exact global solution, a worst-case bound-quality measure is developed. Moreover, the lower bounding (LB) solution is improved to construct a feasible solution, leadin...
• Geometric random edge AI翻译
  作者：Eisenbrand, Friedrich; Vempala, Santosh
  作者单位：Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne; University System of Georgia; Georgia Institute of Technology
  摘要：We show that a variant of the random-edge pivoting rule results in a strongly polynomial time simplex algorithm for linear programs , whose constraint matrix A satisfies a geometric property introduced by Brunsch and Roglin: The sine of the angle of a row of A to a hyperplane spanned by other rows of A is at least . This property is a geometric generalization of A being integral and each sub-determinant of A being bounded by in absolute value. In this case . In particular, linear programs defi...
• Random approximations in multiobjective optimization AI翻译
  作者：Vogel, Silvia
  作者单位：Technische Universitat Ilmenau
  摘要：Often decision makers have to cope with a programming problem with unknown quantitities. Then they will estimate these quantities and solve the problem as it then appears-the 'approximate problem'. Thus there is a need to establish conditions which will ensure that the solutions to the approximate problem will come close to the solutions to the true problem in a suitable manner. Confidence sets, i.e. sets that cover the true sets with a given prescribed probability, provide useful quantitative...
• An exponential lower bound for Cunningham's rule AI翻译
  作者：Avis, David; Friedmann, Oliver
  作者单位：University of Munich; Kyoto University; McGill University
  摘要：In this paper we give an exponential lower bound for Cunningham's least recently considered (round-robin) rule as applied to parity games, Markov decision processes and linear programs. This improves a recent subexponential bound of Friedmann for this rule on these problems. The round-robin rule fixes a cyclical order of the variables and chooses the next pivot variable starting from the previously chosen variable and proceeding in the given circular order. It is perhaps the simplest example f...
• Relative entropy optimization and its applications AI翻译
  作者：Chandrasekaran, Venkat; Shah, Parikshit
  作者单位：California Institute of Technology; California Institute of Technology; University of Wisconsin System; University of Wisconsin Madison
  摘要：In this expository article, we study optimization problems specified via linear and relative entropy inequalities. Such relative entropy programs (REPs) are convex optimization problems as the relative entropy function is jointly convex with respect to both its arguments. Prominent families of convex programs such as geometric programs (GPs), second-order cone programs, and entropy maximization problems are special cases of REPs, although REPs are more general than these classes of problems. W...