-
作者：Adjiashvili, David; Hommelsheim, Felix; Muhlenthaler, Moritz
作者单位：Swiss Federal Institutes of Technology Domain; ETH Zurich; Dortmund University of Technology; Communaute Universite Grenoble Alpes; Institut National Polytechnique de Grenoble; Universite Grenoble Alpes (UGA); Centre National de la Recherche Scientifique (CNRS)
摘要：We introduce and study the problem Flexible Graph Connectivity, which in contrast to many classical connectivity problems features a non-uniform failure model. We distinguish between safe and unsafe resources and postulate that failures can only occur among the unsafe resources. Given an undirected edge-weighted graph and a set of unsafe edges, the task is to find a minimum-cost subgraph that remains connected after removing at most k unsafe edges. We give constant-factor approximation algorit...
-
作者：Morshed, Md Sarowar; Islam, Md Saiful; Noor-E-Alam, Md.
作者单位：Northeastern University
摘要：Randomized Kaczmarz, Motzkin Method and Sampling Kaczmarz Motzkin (SKM) algorithms are commonly used iterative techniques for solving a system of linear inequalities (i.e., Ax <= b). As linear systems of equations represent a modeling paradigm for solving many optimization problems, these randomized and iterative techniques are gaining popularity among researchers in different domains. In this work, we propose a Generalized Sampling Kaczmarz Motzkin (GSKM) method that unifies the iterative met...
-
作者：Huang, Wen; Wei, Ke
作者单位：Xiamen University; Fudan University
摘要：In the Euclidean setting the proximal gradient method and its accelerated variants are a class of efficient algorithms for optimization problems with decomposable objective. In this paper, we develop a Riemannian proximal gradient method (RPG) and its accelerated variant (ARPG) for similar problems but constrained on a manifold. The global convergence of RPG is established under mild assumptions, and the O(1/k) is also derived for RPG based on the notion of retraction convexity. If assuming th...
-
作者：Muir, Christopher; Toriello, Alejandro
作者单位：University System of Georgia; Georgia Institute of Technology
摘要：We propose a dynamic version of the classical node packing problem, also called the stable set or independent set problem. The problem is defined by a node set, a node weight vector, and an edge probability vector. For every pair of nodes, an edge is present or not according to an independent Bernoulli random variable defined by the corresponding entry in the probability vector. At each step, the decision maker selects an available node that maximizes the expected weight of the final packing, ...
-
作者：Molybog, Igor; Sojoudi, Somayeh; Lavaei, Javad
作者单位：University of California System; University of California Berkeley
摘要：In this work, we study the optimization landscape of the non-convex matrix sensing problem that is known to have many local minima in the worst case. Since the existing results are related to the notion of restricted isometry property (RIP) that cannot directly capture the underlying structure of a given problem, they can hardly be applied to real-world problems where the amount of data is not exorbitantly high. To address this issue, we develop the notion of kernel structure property to obtai...
-
作者：Yu, Xian; Shen, Siqian
作者单位：University of Michigan System; University of Michigan
摘要：We study multistage distributionally robust mixed-integer programs under endogenous uncertainty, where the probability distribution of stage-wise uncertainty depends on the decisions made in previous stages. We first consider two ambiguity sets defined by decision-dependent bounds on the first and second moments of uncertain parameters and by mean and covariance matrix that exactly match decision-dependent empirical ones, respectively. For both sets, we show that the subproblem in each stage c...
-
作者：Harks, Tobias; Tan-Timmermans, Veerle
作者单位：RWTH Aachen University
-
作者：Fuellner, Christian; Rebennack, Steffen
作者单位：Helmholtz Association; Karlsruhe Institute of Technology
摘要：We propose a new decomposition method to solve multistage non-convex mixedinteger (stochastic) nonlinear programming problems (MINLPs). We call this algorithm non-convex nested Benders decomposition (NC-NBD). NC-NBD is based on solving dynamically improved mixed-integer linear outer approximations of the MINLP, obtained by piecewise linear relaxations of nonlinear functions. Those MILPs are solved to global optimality using an enhancement of nested Benders decomposition, in which regularizatio...
-
作者：Barman, Siddharth; Fawzi, Omar; Ghoshal, Suprovat; Gurpinar, Emirhan
作者单位：Indian Institute of Science (IISC) - Bangalore; Ecole Normale Superieure de Lyon (ENS de LYON); Inria; Centre National de la Recherche Scientifique (CNRS)
摘要：In the classic maximum coverage problem, we are given subsets T-1,..., T-m of a universe [n] along with an integer k and the objective is to find a subset S subset of [m] of size k that maximizes C(S) := vertical bar boolean OR(i is an element of S) T-i vertical bar. It is well-known that the greedy algorithm for this problem achieves an approximation ratio of (1- e(-1)) and there is a matching inapproximability result. We note that in themaximum coverage problem if an element e is an element ...
-
作者：Paat, Joseph; Schloeter, Miriam; Weismantel, Robert
作者单位：University of British Columbia; Swiss Federal Institutes of Technology Domain; ETH Zurich
摘要：We introduce the integrality number of an integer program (IP). Roughly speaking, the integrality number is the smallest number of integer constraints needed to solve an IP via a mixed integer (MIP) relaxation. One notable property of this number is its invariance under unimodular transformations of the constraint matrix. Considering the largest minor Delta of the constraint matrix, our analysis allows us to make statements of the following form: there exists a number tau(Delta) such that an I...
