-
作者：Jansen, Klaus; Klein, Kim-Manuel; Lassota, Alexandra
作者单位：University of Kiel; Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne
摘要：We consider fundamental algorithmic number theoretic problems and their relation to a class of block structured Integer Linear Programs (ILPs) called 2-stage stochastic. A 2-stage stochastic ILP is an integer program of the form min{c(T)x vertical bar Ax = b, l <= x <= u, x is an element of Z(r+ns)} where the constraint matrix A is an element of Z(ntxr+ns) consists of n matrices A(i) is an element of Z(txs )on the vertical line and n matrices B-i is an element of Z(txs )on the diagonal line as...
-
作者：Chakrabarty, Deeparnab; Negahbani, Maryam
作者单位：Dartmouth College
摘要：In the non-uniform k-center problem, the objective is to cover points in a metric space with specified number of balls of different radii. Chakrabarty, Goyal, and Krishnaswamy [ICALP 2016, Trans. on Algs. 2020] (CGK, henceforth) give a constant factor approximation when there are two types of radii. In this paper, we give a constant factor approximation for the two radii case in the presence of outliers. To achieve this, we need to bypass the technical barrier of bad integrality gaps in the CG...
-
作者：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...
-
作者：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).
-
作者：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...
-
作者：Gahururu, Deborah B.; Hintermueller, Michael; Surowiec, Thomas M.
作者单位：Philipps University Marburg; Leibniz Association; Weierstrass Institute for Applied Analysis & Stochastics; Humboldt University of Berlin
摘要：A class of risk-neutral generalized Nash equilibrium problems is introduced in which the feasible strategy set of each player is subject to a common linear elliptic partial differential equation with random inputs. In addition, each player's actions are taken from a bounded, closed, and convex set on the individual strategies and a bound constraint on the common state variable. Existence of Nash equilibria and first-order optimality conditions are derived by exploiting higher integrability and...
-
作者：de Lima, Vinicius Loti; Iori, Manuel; Miyazawa, Flavio Keidi
作者单位：Universidade Estadual de Campinas; Universita di Modena e Reggio Emilia
摘要：We address the solution of Mixed Integer Linear Programming (MILP) models with strong relaxations that are derived from Dantzig-Wolfe decompositions and allow a pseudo-polynomial pricing algorithm. We exploit their network-flow characterization and provide a framework based on column generation, reduced-cost variable-fixing, and a highly asymmetric branching scheme that allows us to take advantage of the potential of the current MILP solvers. We apply our framework to a variety of cutting and ...
-
作者：Gomez, Andres; He, Ziyu; Pang, Jong-Shi
作者单位：University of Southern California
摘要：This paper studies several versions of the sparse optimization problem in statistical estimation defined by a pairwise separation objective. The sparsity (i.e., l(0)) function is approximated by a folded concave function; the pairwise separation gives rise to an objective of the Z-type. After presenting several realistic estimation problems to illustrate the Z-structure, we introduce a linear-step inner-outer loop algorithm for computing a directional stationary solution of the nonconvex nondi...
-
作者：Cui, Shisheng; Shanbhag, Uday, V
作者单位：Pennsylvania Commonwealth System of Higher Education (PCSHE); Pennsylvania State University; Pennsylvania State University - University Park
摘要：We consider a class of noncooperative hierarchical N-player games where the ith player solves a parametrized stochastic mathematical program with equilibrium constraints (MPEC) with the caveat that the implicit form of the ith player's in MPEC is convex in player strategy, given rival decisions. Few, if any, general purpose schemes exist for computing equilibria, motivating the development of computational schemes in two regimes: (a) Monotone regimes. When player-specific implicit problems are...
-
作者：Davis, Damek Shea; Guenluek, Oktay; Kaibel, Volker; Nannicini, Giacomo; Yuan, Xa-Xiang
作者单位：Cornell University; Otto von Guericke University; University of Southern California; Chinese Academy of Sciences
