-
作者：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.
-
作者：Jiang, Bo; Dai, Yu-Hong
作者单位：Chinese Academy of Sciences; Academy of Mathematics & System Sciences, CAS
摘要：This paper considers optimization problems on the Stiefel manifold (XX)-X-T = I-p, where X is an element of R-nxp is the variable and I-p is the p-by-p identity matrix. A framework of constraint preserving update schemes is proposed by decomposing each feasible point into the range space of X and the null space of X-T. While this general framework can unify many existing schemes, a new update scheme with low complexity cost is also discovered. Then we study a feasible Barzilai-Borwein-like met...
-
作者：Nie, Jiawang
作者单位：University of California System; University of California San Diego
摘要：This paper studies the hierarchy of local minimums of a polynomial in the vector space . For this purpose, we first compute -minimums, for which the first and second order necessary optimality conditions are satisfied. To compute each -minimum, we construct a sequence of semidefinite relaxations, based on optimality conditions. We prove that each constructed sequence has finite convergence, under some generic conditions. A procedure for computing all local minimums is given. When there are equ...
-
作者：Pena, Javier; Vera, Juan C.; Zuluaga, Luis F.
作者单位：Carnegie Mellon University; Tilburg University; Lehigh University
摘要：Polynomial optimization encompasses a very rich class of problems in which both the objective and constraints can be written in terms of polynomials on the decision variables. There is a well established body of research on quadratic polynomial optimization problems based on reformulations of the original problem as a conic program over the cone of completely positive matrices, or its conic dual, the cone of copositive matrices. As a result of this reformulation approach, novel solution scheme...
-
作者：Chatzipanagiotis, Nikolaos; Dentcheva, Darinka; Zavlanos, Michael M.
作者单位：Duke University; Stevens Institute of Technology
摘要：We propose a novel distributed method for convex optimization problems with a certain separability structure. The method is based on the augmented Lagrangian framework. We analyze its convergence and provide an application to two network models, as well as to a two-stage stochastic optimization problem. The proposed method compares favorably to two augmented Lagrangian decomposition methods known in the literature, as well as to decomposition methods based on the ordinary Lagrangian function.
-
作者：King, Douglas M.; Jacobson, Sheldon H.; Sewell, Edward C.
作者单位：University of Illinois System; University of Illinois Urbana-Champaign; University of Illinois System; University of Illinois Urbana-Champaign; Southern Illinois University System; Southern Illinois University Edwardsville
摘要：Graph partitioning is an intractable problem that arises in many practical applications. Heuristics such as local search generate good (though suboptimal) solutions in limited time. Such heuristics must be able to explore the solution space quickly and, when the solution space is constrained, differentiate feasible solutions from infeasible ones. Geographic zoning problems allocate some resource (e.g., political representation, school enrollment, police patrols) to contiguous zones modeled by ...
-
作者：Letchford, Adam N.; Lasserre, Jean B.; Parrilo, Pablo A.; Steurer, David
作者单位：Lancaster University; Centre National de la Recherche Scientifique (CNRS); Massachusetts Institute of Technology (MIT); Cornell University
-
作者：Caprara, Alberto; Dell'Amico, Mauro; Diaz-Diaz, Jose Carlos; Iori, Manuel; Rizzi, Romeo
作者单位：Universita di Modena e Reggio Emilia; University of Verona
摘要：It is well known that the gap between the optimal values of bin packing and fractional bin packing, if the latter is rounded up to the closest integer, is almost always null. Known counterexamples to this for integer input values involve fairly large numbers. Specifically, the first one was derived in 1986 and involved a bin capacity of the order of a billion. Later in 1998 a counterexample with a bin capacity of the order of a million was found. In this paper we show a large number of counter...
