-
作者：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 ...
-
作者：Adjiashvili, David; Stiller, Sebastian; Zenklusen, Rico
作者单位：Swiss Federal Institutes of Technology Domain; ETH Zurich; Technical University of Berlin; Swiss Federal Institutes of Technology Domain; ETH Zurich; Johns Hopkins University
摘要：We commence an algorithmic study of Bulk-Robustness, a new model of robustness in combinatorial optimization. Unlike most existing models, Bulk-Robust combinatorial optimization features a highly nonuniform failure model. Instead of an interdiction budget, Bulk-Robust counterparts provide an explicit list of interdiction sets, comprising the admissible set of scenarios, thus allowing to model correlations between failures of different components in the system, interdiction sets of variable car...
-
作者：Golovin, Daniel; Goyal, Vineet; Polishchuk, Valentin; Ravi, R.; Sysikaski, Mikko
作者单位：Alphabet Inc.; Google Incorporated; Alphabet Inc.; Google Incorporated; University of Helsinki; Carnegie Mellon University
摘要：In this paper, we study the robust and stochastic versions of the two-stage min-cut and shortest path problems introduced in Dhamdhere et al. (in How to pay, come what may: approximation algorithms for demand-robust covering problems. In: FOCS, pp 367-378, 2005), and give approximation algorithms with improved approximation factors. Specifically, we give a 2-approximation for the robust min-cut problem and a 4-approximation for the stochastic version. For the two-stage shortest path problem, w...
-
作者：Lau, Lap Chi; Zhou, Hong
作者单位：Chinese University of Hong Kong
摘要：We present an approximation algorithm for the minimum bounded degree Steiner network problem that returns a Steiner network of cost at most two times the optimal and the degree on each vertex is at most , where is the maximum connectivity requirement and is the given degree bound on . This unifies, simplifies, and improves the previous results for this problem.
