-
作者：Kaibel, Volker; Weltge, Stefan
作者单位：Otto von Guericke University
摘要：Let be the set of integer points in some polyhedron. We investigate the smallest number of facets of any polyhedron whose set of integer points is . This quantity, which we call the relaxation complexity of , corresponds to the smallest number of linear inequalities of any integer program having as the set of feasible solutions that does not use auxiliary variables. We show that the use of auxiliary variables is essential for constructing polynomial size integer programming formulations in man...
-
作者：Mnich, Matthias; Wiese, Andreas
作者单位：Max Planck Society
摘要：Fixed-parameter tractability analysis and scheduling are two core domains of combinatorial optimization which led to deep understanding of many important algorithmic questions. However, even though fixed-parameter algorithms are appealing for many reasons, no such algorithms are known for many fundamental scheduling problems. In this paper we present the first fixed-parameter algorithms for classical scheduling problems such as makespan minimization, scheduling with job-dependent cost function...
-
作者：Carnes, Tim; Shmoys, David B.
作者单位：Cornell University; Cornell University
摘要：Primal-dual algorithms have played an integral role in recent developments in approximation algorithms, and yet there has been little work on these algorithms in the context of LP relaxations that have been strengthened by the addition of more sophisticated valid inequalities. We introduce primal-dual schema based on the LP relaxations devised by Carr et al. for the minimum knapsack problem as well as for the single-demand capacitated facility location problem. Our primal-dual algorithms achie...
-
作者：Kaibel, Volker; Thomas, Rekha
作者单位：Otto von Guericke University; University of Washington; University of Washington Seattle
-
作者：Gupta, A.; Koenemann, J.; Leonardi, S.; Ravi, R.; Schaefer, G.
作者单位：Carnegie Mellon University; University of Waterloo; Sapienza University Rome; Centrum Wiskunde & Informatica (CWI); Vrije Universiteit Amsterdam
摘要：We consider the problem of designing efficient mechanisms to share the cost of providing some service to a set of self-interested customers. In this paper, we mainly focus on cost functions that are induced by prize-collecting optimization problems. Such cost functions arise naturally whenever customers can be served in two different ways: either by being part of a common service solution or by being served individually. One of our main contributions is a general lifting technique that allows ...
-
作者：Peng, Jiming; Zhu, Tao
作者单位：University of Houston System; University of Houston; University of Illinois System; University of Illinois Urbana-Champaign
摘要：In this paper, we consider the so-called worst-case linear optimization (WCLO) with uncertainties in the right-hand-side of the constraints. Such a problem arises from numerous applications such as systemic risk estimate in finance and stochastic optimization. We first show the problem is NP-hard and present a coarse semidefinite relaxation (SDR) for WCLO. An iterative procedure is introduced to sequentially refine the relaxation model based on the solution of the current relaxation model by s...
-
作者：Asamov, Tsvetan; Ruszczynski, Andrzej
作者单位：Princeton University; Rutgers University System; Rutgers University New Brunswick
摘要：In this paper we study the concept of time consistency as it relates to multistage risk-averse stochastic optimization problems on finite scenario trees. We use dynamic time-consistent formulations to approximate problems having a single coherent risk measure applied to the aggregated costs over all time periods. The dual representation of coherent risk measures is used to create a time-consistent cutting plane algorithm. Additionally, we also develop methods for the construction of universal ...
-
作者：Faenza, Yuri; Fiorini, Samuel; Grappe, Roland; Tiwary, Hans Raj
作者单位：Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne; Universite Libre de Bruxelles; Centre National de la Recherche Scientifique (CNRS); Universite Paris 13; Charles University Prague
摘要：An extended formulation of a polyhedron is a linear description of a polyhedron together with a linear map such that . These objects are of fundamental importance in polyhedral combinatorics and optimization theory, and the subject of a number of studies. Yannakakis' factorization theorem (Yannakakis in J Comput Syst Sci 43(3):441-466, 1991) provides a surprising connection between extended formulations and communication complexity, showing that the smallest size of an extended formulation of ...
-
作者：van Dam, Edwin R.; Sotirov, Renata
作者单位：Tilburg University
摘要：The graph partition problem is the problem of partitioning the vertex set of a graph into a fixed number of sets of given sizes such that the sum of weights of edges joining different sets is optimized. In this paper we simplify a known matrix-lifting semidefinite programming relaxation of the graph partition problem for several classes of graphs and also show how to aggregate additional triangle and independent set constraints for graphs with symmetry. We present an eigenvalue bound for the g...
-
作者：Jiang, Bo; Ma, Shiqian; Zhang, Shuzhong
作者单位：Shanghai University of Finance & Economics; Chinese University of Hong Kong; University of Minnesota System; University of Minnesota Twin Cities
摘要：This paper is concerned with the computation of the principal components for a general tensor, known as the tensor principal component analysis (PCA) problem. We show that the general tensor PCA problem is reducible to its special case where the tensor in question is super-symmetric with an even degree. In that case, the tensor can be embedded into a symmetric matrix. We prove that if the tensor is rank-one, then the embedded matrix must be rank-one too, and vice versa. The tensor PCA problem ...
