-
作者：Oba, Ryoshun; Tanigawa, Shin-ichi
作者单位：University of Tokyo
摘要：A tensegrity is a structure made from cables, struts, and stiff bars. A d-dimensional tensegrity is universally rigid if it is rigid in any dimension d' with d' >= d. The celebrated super stability condition due to Connelly gives a sufficient condition for a tensegrity to be universally rigid. Gortler and Thurston showed that super stability characterizes universal rigidity when the point configuration is generic and everymember is a stiff bar. We extend this result in two directions. We first...
-
作者：Borst, Sander; Dadush, Daniel; Huiberts, Sophie; Tiwari, Samarth
作者单位：Centrum Wiskunde & Informatica (CWI)
摘要：For a binary integer program (IP) max c(T)x, Ax <= b, x is an element of {0, 1}(n), where A is an element of R-mxn and c is an element of R-n have independent Gaussian entries and the right-hand side b is an element of R-m satisfies that its negative coordinates have l(2) norm at most n/10, we prove that the gap between the value of the linear programming relaxation and the IP is upper bounded by poly(m)(log n)(2)/n with probability at least 1 - 2/n(7) - 2(-poly(m)). Our results give a Gaussia...
-
作者：Bertsimas, Dimitris; Cory-Wright, Ryan; Pauphilet, Jean
作者单位：Massachusetts Institute of Technology (MIT); Imperial College London; International Business Machines (IBM); IBM USA; University of London; London Business School
摘要：A key question in many low-rank problems throughout optimization, machine learning, and statistics is to characterize the convex hulls of simple low-rank sets and judiciously apply these convex hulls to obtain strong yet computationally tractable relaxations. We invoke the matrix perspective function-the matrix analog of the perspective function-to characterize explicitly the convex hull of epigraphs of simple matrix convex functions under low-rank constraints. Further, we combine the matrix p...
-
作者：Del Pia, Alberto; Ma, Mingchen
作者单位：University of Wisconsin System; University of Wisconsin Madison; University of Wisconsin System; University of Wisconsin Madison
摘要：We study exact recovery conditions for the linear programming relaxation of the k-median problem in the stochastic ball model (SBM). In Awasthi et al. (Relax, no need to round: integrality of clustering formulations. arXiv:1408.4045, 2015; in: Proceedings of the 2015 conference on innovations in theoretical computer science, pp 191-200, 2015), the authors give a tight result for the k-median LP in the SBM, saying that exact recovery can be achieved as long as the balls are pairwise disjoint. W...
-
作者：Dussault, Jean-Pierre; Gilbert, Jean Charles
作者单位：University of Sherbrooke
摘要：This paper considers the balanced form of the standard linear complementarity problem with unique solution and provides a more precise expression of an upper error bound discovered by Chen and Xiang and published in 2006. This expression has at least two advantages. It makes possible the exact computation of the error bound factor and it provides a satisfactory upper estimate of that factor in terms of the data bitlength when the data is formed of rational numbers. Along the way, we show that,...
-
作者：Basu, Amitabh
作者单位：Johns Hopkins University
摘要：In the first part of this paper, we present a unified framework for analyzing the algorithmic complexity of any optimization problem, whether it be continuous or discrete in nature. This helps to formalize notions like input, size and complexity in the context of general mathematical optimization, avoiding context dependent definitions which is one of the sources of difference in the treatment of complexity within continuous and discrete optimization. In the second part of the paper, we employ...
-
作者：Zhang, Zeyang; Gao, Chuanhou; Luedtke, James
作者单位：Zhejiang University; University of Wisconsin System; University of Wisconsin Madison
摘要：We study the static joint chance-constrained lot-sizing problem, in which production decisions over a planning horizon are made before knowing random future demands, and the inventory variables are then determined by the demand realizations. The joint chance constraint imposes a service level requirement that the probability that all demands are met on time be above a threshold. We model uncertain outcomes with a finite set of scenarios and begin by applying existing results about chance-const...
-
作者：Oliveira, Roberto, I; Thompson, Philip
作者单位：Purdue University System; Purdue University; Purdue University System; Purdue University
摘要：We derive new and improved non-asymptotic deviation inequalities for the sample average approximation (SAA) of an optimization problem. Our results give strong error probability bounds that are sub-Gaussian even when the randomness of the problem is fairly heavy tailed. Additionally, we obtain good (often optimal) dependence on the sample size and geometrical parameters of the problem. Finally, we allow for random constraints on the SAA and unbounded feasible sets, which also do not seem to ha...
-
作者：Song, Dogyoon; Parrilo, Pablo A.
作者单位：University of Michigan System; University of Michigan; Massachusetts Institute of Technology (MIT)
摘要：We study the problem of approximating the cone of positive semidefinite (PSD) matrices with a cone that can be described by smaller-sized PSD constraints. Specifically, we ask the question: how closely can we approximate the set of unit-trace nxn PSD matrices, denoted by D, using at most N number of k x k PSD constraints? In this paper, we prove lower bounds on N to achieve a good approximation of D by considering two constructions of an approximating set. First, we consider the unit-trace nxn...
-
作者：Averkov, Gennadiy; Hojny, Christopher; Schymura, Matthias
作者单位：Brandenburg University of Technology Cottbus; Eindhoven University of Technology
摘要：The relaxation complexity rc(X) of the set of integer points X contained in a polyhedron is the smallest number of facets of any polyhedron P such that the integer points in P coincide with X. It is a useful tool to investigate the existence of compact linear descriptions of X. In this article, we derive tight and computable upper bounds on rc(Q)(X), a variant of rc(X) in which the polyhedra P are required to be rational, and we show that rc(X) can be computed in polynomial time if X is 2-dime...
