-
作者：Bertsimas, Dimitris; Goyal, Vineet; Lu, Brian Y.
作者单位：Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT); Columbia University
摘要：In this paper, we study the performance of static solutions for two-stage adjustable robust linear optimization problems with uncertain constraint and objective coefficients and give a tight characterization of the adaptivity gap. Computing an optimal adjustable robust optimization problem is often intractable since it requires to compute a solution for all possible realizations of uncertain parameters (Feige et al. in Lect Notes Comput Sci 4513:439-453, 2007). On the other hand, a static solu...
-
作者：Locatelli, Marco
作者单位：University of Parma
摘要：The Lovasz and Lovasz-Schrijver bounds are well known upper bounds for the clique number of a graph, based on the solution of semidefinite programming problems. Both bounds can be seen as obtained through a relaxation of a completely positive formulation of the maximum clique problem. In this paper we propose to improve these bounds by adding inequalities based on independent sets, which may be non-valid, in the sense that they may be violated by optimal solutions of the completely positive fo...
-
作者：Correa, Jose; Marchetti-Spaccamela, Alberto; Matuschke, Jannik; Stougie, Leen; Svensson, Ola; Verdugo, Victor; Verschae, Jose
作者单位：Universidad de Chile; Sapienza University Rome; Technical University of Berlin; Vrije Universiteit Amsterdam; Centrum Wiskunde & Informatica (CWI); Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne; Pontificia Universidad Catolica de Chile; Pontificia Universidad Catolica de Chile
摘要：A natural extension of the makespan minimization problem on unrelated machines is to allow jobs to be partially processed by different machines while incurring an arbitrary setup time. In this paper we present increasingly stronger LP-relaxations for this problem and their implications on the approximability of the problem. First we show that the straightforward LP, extending the approach for the original problem, has an integrality gap of 3 and yields an approximation algorithm of the same fa...
-
作者：Marchetti-Spaccamela, Alberto; Rutten, Cyriel; van der Ster, Suzanne; Wiese, Andreas
作者单位：Sapienza University Rome; Maastricht University; Vrije Universiteit Amsterdam; Max Planck Society
摘要：We study the problem of assigning sporadic tasks to unrelated machines such that the tasks on each machine can be feasibly scheduled. Despite its importance for modern real-time systems, this problem has not been studied before. We present a polynomial-time algorithm which approximates the problem with a constant speedup factor of and show that any polynomial-time algorithm needs a speedup factor of at least , unless P NP. In the case of a constant number of machines we give a polynomial-time ...
-
作者：Waldspurger, Irene; d'Aspremont, Alexandre; Mallat, Stephane
作者单位：Universite PSL; Ecole Normale Superieure (ENS); Universite PSL; Ecole Normale Superieure (ENS); Centre National de la Recherche Scientifique (CNRS); Universite PSL; Ecole Normale Superieure (ENS); Centre National de la Recherche Scientifique (CNRS); CNRS - Institute for Information Sciences & Technologies (INS2I)
摘要：Phase retrieval seeks to recover a signal from the amplitude of linear measurements . We cast the phase retrieval problem as a non-convex quadratic program over a complex phase vector and formulate a tractable relaxation (called PhaseCut) similar to the classical MaxCut semidefinite program. We solve this problem using a provably convergent block coordinate descent algorithm whose structure is similar to that of the original greedy algorithm in Gerchberg and Saxton (Optik 35:237-246, 1972), wh...
-
作者：Bertsimas, Dimitris; Bidkhori, Hoda
作者单位：Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT)
摘要：We consider two-stage adjustable robust linear optimization problems with uncertain right hand side b belonging to a convex and compact uncertainty set u. We provide an a priori approximation bound on the ratio of the optimal affine (in b) solution to the optimal adjustable solution that depends on two fundamental geometric properties of u: (a) the symmetry and (b) the simplex dilation factor of the uncertainty set u and provides deeper insight on the power of affine policies for this class of...
-
作者：Fawzi, Hamza; Gouveia, Joao; Parrilo, Pablo A.; Robinson, Richard Z.; Thomas, Rekha R.
作者单位：Massachusetts Institute of Technology (MIT); Universidade de Coimbra; University of Washington; University of Washington Seattle
摘要：Let M is an element of R-pxq be a nonnegative matrix. The positive semidefinite rank (psd rank) of M is the smallest integer k for which there exist positive semidefinite matrices of size such that . The psd rank has many appealing geometric interpretations, including semidefinite representations of polyhedra and information-theoretic applications. In this paper we develop and survey the main mathematical properties of psd rank, including its geometry, relationships with other rank notions, an...
-
作者：Goemans, Michel X.
作者单位：Massachusetts Institute of Technology (MIT)
摘要：In this note, we consider the permutahedron, the convex hull of all permutations of . We show how to obtain an extended formulation for this polytope from any sorting network. By using the optimal Ajtai-Komls-Szemer,di sorting network, this extended formulation has variables and inequalities. Furthermore, from basic polyhedral arguments, we show that this is best possible (up to a multiplicative constant) since any extended formulation has at least inequalities. The results easily extend to th...
-
作者：Leovey, H.; Roemisch, W.
作者单位：Humboldt University of Berlin
摘要：Quasi-Monte Carlo (QMC) algorithms are studied for generating scenarios to solve two-stage linear stochastic programming problems. Their integrands are piecewise linear-quadratic, but do not belong to the function spaces considered for QMC error analysis. We show that under some weak geometric condition on the two-stage model all terms of their ANOVA decomposition, except the one of highest order, are continuously differentiable and second order mixed derivatives exist almost everywhere and be...
-
作者：Pang, C. H. Jeffrey
作者单位：National University of Singapore
摘要：We study how the supporting hyperplanes produced by the projection process can complement the method of alternating projections and its variants for the convex set intersection problem. For the problem of finding the closest point in the intersection of closed convex sets, we propose an algorithm that, like Dykstra's algorithm, converges strongly in a Hilbert space. Moreover, this algorithm converges in finitely many iterations when the closed convex sets are cones in satisfying an alignment c...
