-
作者：Daboul, Siad; Held, Stephan; Vygen, Jens
作者单位：University of Bonn; University of Bonn
摘要：We revisit the deadline version of the discrete time-cost tradeoff problem for the special case of bounded depth. Such instances occur for example in VLSI design. The depth of an instance is the number of jobs in a longest chain and is denoted by d. We prove new upper and lower bounds on the approximability. First we observe that the problem can be regarded as a special case of finding aminimum-weight vertex cover in a d-partite hypergraph. Next, we study the natural LP relaxation, which can b...
-
作者：Legault, Robin; Cote, Jean-Francois; Gendron, Bernard
作者单位：Laval University; Universite de Montreal; Universite de Montreal
摘要：The single-sink fixed-charge transportation problem is known to have many applications in the area of manufacturing and transportation as well as being an important subproblem of the fixed-charge transportation problem. However, even the best algorithms from the literature do not fully leverage the structure of this problem, to the point of being surpassed by modern general-purpose mixed-integer programming solvers for large instances. We introduce a novel reformulation of the problem and stud...
-
作者：Royset, Johannes O.
作者单位：United States Department of Defense; United States Navy; Naval Postgraduate School
摘要：Approximations of optimization problems arise in computational procedures and sensitivity analysis. The resulting effect on solutions can be significant, with even small approximations of components of a problem translating into large errors in the solutions. We specify conditions under which approximations are well behaved in the sense of minimizers, stationary points, and level-sets and this leads to a framework of consistent approximations. The framework is developed for a broad class of co...
-
作者：Sun, Hailin; Shapiro, Alexander; Chen, Xiaojun
作者单位：Nanjing Normal University; University System of Georgia; Georgia Institute of Technology; Hong Kong Polytechnic University
摘要：We propose a formulation of the distributionally robust variational inequality (DRVI) to deal with uncertainties of distributions of the involved random variables in variational inequalities. Examples of the DRVI are provided, including the optimality conditions for distributionally robust optimization and distributionally robust games (DRG). The existence of solutions and monotonicity of the DRVI are discussed. Moreover, we propose a sample average approximation (SAA) approach to the DRVI and...
-
作者：Blauth, Jannis; Traub, Vera; Vygen, Jens
作者单位：University of Bonn; University of Bonn; Swiss Federal Institutes of Technology Domain; ETH Zurich
摘要：We devise a new approximation algorithm for capacitated vehicle routing. Our algorithm yields a better approximation ratio for general capacitated vehicle routing as well as for the unit-demand case and the splittable variant. Our results hold in arbitrary metric spaces. This is the first improvement upon the classical tour partitioning algorithm by Haimovich and Rinnooy Kan (Math Oper Res 10:527-542, 1985) and Altinkemer and Gavish (Oper Res Lett 6:149-158, 1987).
-
作者：Basu, Amitabh; Jiang, Hongyi
作者单位：Johns Hopkins University
摘要：We define a new cutting plane closure for pure integer programs called the two-halfspace closure. It is a natural generalization of the well-known Chvatal-Gomory closure. We prove that the two-halfspace closure is polyhedral. We also study the corresponding two-halfspace rank of any valid inequality and show that it is at most the split rank of the inequality. Moreover, while the split rank can be strictly larger than the two-halfspace rank, the split rank is at most twice the two-halfspace ra...
-
作者：Zamani, Moslem; Hladik, Milan
作者单位：Tilburg University; Charles University Prague
摘要：Due to their relation to the linear complementarity problem, absolute value equations have been intensively studied recently. In this paper, we present error bound conditions for absolute value equations. Along with the error bounds, we introduce a condition number. We consider general scaled matrix p-norms, as well as particular p-norms. We discuss basic properties of the condition number, including its computational complexity. We present various bounds on the condition number, and we give e...
-
作者：Eberle, Franziska; Hoeksma, Ruben; Megow, Nicole; Noelke, Lukas; Schewior, Kevin; Simon, Bertrand
作者单位：University of London; London School Economics & Political Science; University of Twente; University of Bremen; University of Southern Denmark; Centre National de la Recherche Scientifique (CNRS); CNRS - National Institute of Nuclear and Particle Physics (IN2P3)
摘要：The speed-robust scheduling problem is a two-stage problem where, given m machines, jobs must be grouped into at most m bags while the processing speeds of the machines are unknown. After the speeds are revealed, the grouped jobs must be assigned to the machines without being separated. To evaluate the performance of algorithms, we determine upper bounds on the worst-case ratio of the algorithm's makespan and the optimal makespan given full information. We refer to this ratio as the robustness...
-
作者：Juditsky, Anatoli; Kwon, Joon; Moulines, Eric
作者单位：Communaute Universite Grenoble Alpes; Universite Grenoble Alpes (UGA); AgroParisTech; INRAE; Universite Paris Saclay; Institut Polytechnique de Paris; Ecole Polytechnique
摘要：We introduce and analyze a new family of first-order optimization algorithms which generalizes and unifies both mirror descent and dual averaging. Within the framework of this family, we define new algorithms for constrained optimization that combines the advantages of mirror descent and dual averaging. Our preliminary simulation study shows that these new algorithms significantly outperform available methods in some situations.
-
作者：Garrigos, Guillaume; Rosasco, Lorenzo; Villa, Silvia
作者单位：Centre National de la Recherche Scientifique (CNRS); Universite Paris Cite; University of Genoa; Istituto Italiano di Tecnologia - IIT; University of Genoa
摘要：We provide a comprehensive study of the convergence of the forward-backward algorithm under suitable geometric conditions, such as conditioning or Lojasiewicz properties. These geometrical notions are usually local by nature, and may fail to describe the fine geometry of objective functions relevant in inverse problems and signal processing, that have a nice behaviour on manifolds, or sets open with respect to a weak topology. Motivated by this observation, we revisit those geometric notions o...
