-
作者：Chen, Lin; Eberle, Franziska; Megow, Nicole; Schewior, Kevin; Stein, Cliff
作者单位：Texas Tech University System; Texas Tech University; University of Bremen; University of Cologne; Columbia University
摘要：We study a fundamental online job admission problem where jobs with deadlines arrive online over time at their release dates, and the task is to determine a preemptive single-server schedule which maximizes the number of jobs that complete on time. To circumvent known impossibility results, we make a standard slackness assumption by which the feasible time window for scheduling a job is at least 1+epsilon times its processing time, for some epsilon>0. We quantify the impact that different prov...
-
作者：Qian, Xun; Liao, Li-Zhi; Sun, Jie
作者单位：Hong Kong Baptist University; Curtin University; National University of Singapore
摘要：The affine scaling algorithm is one of the earliest interior point methods developed for linear programming. This algorithm is simple and elegant in terms of its geometric interpretation, but it is notoriously difficult to prove its convergence. It often requires additional restrictive conditions such as nondegeneracy, specific initial solutions, and/or small step length to guarantee its global convergence. This situation is made worse when it comes to applying the affine scaling idea to the s...
-
作者：Attouch, Hedy; Cabot, Alexandre
作者单位：Universite de Montpellier; Universite Bourgogne Europe; Centre National de la Recherche Scientifique (CNRS); CNRS - National Institute for Mathematical Sciences (INSMI)
摘要：In a Hilbert spaceHgivenA:H -> 2Ha maximally monotone operator, we study the convergence properties of a general class of relaxed inertial proximal algorithms. This study aims to extend to the case of the general monotone inclusionAxCONTAINS AS MEMBER0the acceleration techniques initially introduced by Nesterov in the case of convex minimization. The relaxed form of the proximal algorithms plays a central role. It comes naturally with the regularization of the operatorAby its Yosida approximat...
-
作者：Fernandez, Damian; Solodov, Mikhail
作者单位：Consejo Nacional de Investigaciones Cientificas y Tecnicas (CONICET); National University of Cordoba; National University of Cordoba
摘要：At each iteration of the augmented Lagrangian algorithm, a nonlinear subproblem is being solved. The number of inner iterations (of some/any method) needed to obtain a solution of the subproblem, or even a suitable approximate stationary point, is in principle unknown. In this paper we show that to compute an approximate stationary point sufficient to guarantee local superlinear convergence of the augmented Lagrangian iterations, it is enough to solve two quadratic programming problems (or two...
-
作者：Royset, Johannes O.
作者单位：United States Department of Defense; United States Navy; Naval Postgraduate School
摘要：Upper semicontinuous (usc) functions arise in the analysis of maximization problems, distributionally robust optimization, and function identification, which includes many problems of nonparametric statistics. We establish that every usc function is the limit of a hypo-converging sequence of piecewise affine functions of the difference-of-max type and illustrate resulting algorithmic possibilities in the context of approximate solution of infinite-dimensional optimization problems. In an effor...
-
作者：Cheriyan, J.; Dippel, J.; Grandoni, F.; Khan, A.; Narayan, V. V.
作者单位：University of Waterloo; Universita della Svizzera Italiana; Indian Institute of Science (IISC) - Bangalore; McGill University
摘要：We present a 7/4 approximation algorithm for the matching augmentation problem (MAP): given a multi-graph with edges of cost either zero or one such that the edges of cost zero form a matching, find a 2-edge connected spanning subgraph (2-ECSS) of minimum cost. We first present a reduction of any givenMAP instance to a collection of well-structured MAP instances such that the approximation guarantee is preserved. Then we present a 7/4 approximation algorithm for awell-structuredMAPinstance. Th...
-
作者：Bendotti, Pascale; Fouilhoux, Pierre; Rottner, Cecile
作者单位：Sorbonne Universite; Electricite de France (EDF)
摘要：We consider integer linear programs whose solutions are binary matrices and whose (sub-)symmetry groups are symmetric groups acting on (sub-)columns. Such structured sub-symmetry groups arise in important classes of combinatorial problems, e.g. graph coloring or unit commitment. For a priori known (sub-)symmetries, we propose a framework to build (sub-)symmetry-breaking inequalities for such problems, by introducing one additional variable per considered sub-symmetry group. The derived inequal...
-
作者：O'Connor, Daniel; Vandenberghe, Lieven
作者单位：University of San Francisco; University of California System; University of California Los Angeles
摘要：The primal-dual hybrid gradient (PDHG) algorithm proposed by Esser, Zhang, and Chan, and by Pock, Cremers, Bischof, and Chambolle is known to include as a special case the Douglas-Rachford splitting algorithm for minimizing the sum of two convex functions. We show that, conversely, the PDHG algorithm can be viewed as a special case of the Douglas-Rachford splitting algorithm.
-
作者：Aprile, Manuel; Faenza, Yuri
作者单位：Universite Libre de Bruxelles; Columbia University
摘要：Deterministic protocols are well-known tools to obtain extended formulations, with many applications to polytopes arising in combinatorial optimization. Although constructive, those tools are not output-efficient, since the time needed to produce the extended formulation also depends on the number of rows of the slack matrix (hence, on the exact description in the original space). We give general sufficient conditions under which those tools can be implemented as to be output-efficient, showin...
-
作者：Gaar, Elisabeth; Rendl, Franz
作者单位：University of Klagenfurt
摘要：The exact subgraph approach was recently introduced as a hierarchical scheme to get increasingly tight semidefinite programming relaxations of several NP-hard graph optimization problems. Solving these relaxations is a computational challenge because of the potentially large number of violated subgraph constraints. We introduce a computational framework for these relaxations designed to cope with these difficulties. We suggest a partial Lagrangian dual, and exploit the fact that its evaluation...
