-
作者：Buchbinder, Niv; Coester, Christian; Naor, Joseph
作者单位：Tel Aviv University; University of Sheffield; Technion Israel Institute of Technology
摘要：We consider the online k-taxi problem, a generalization of the k-server problem, in which k servers are located in a metric space. A sequence of requests is revealed one by one, where each request is a pair of two points, representing the start and destination of a travel request by a passenger. The goal is to serve all requests while minimizing the distance traveled without carrying a passenger. We show that the classic Double Coverage algorithm has competitive ratio 2(k) - 1 on HSTs, matchin...
-
作者：Baraldi, Robert J. J.; Kouri, Drew P. P.
作者单位：United States Department of Energy (DOE); Sandia National Laboratories
摘要：Many applications require minimizing the sum of smooth and nonsmooth functions. For example, basis pursuit denoising problems in data science require minimizing a measure of data misfit plus an l(1)-regularizer. Similar problems arise in the optimal control of partial differential equations (PDEs) when sparsity of the control is desired. We develop a novel trust-region method to minimize the sum of a smooth nonconvex function and a nonsmooth convex function. Our method is unique in that it per...
-
作者：Angelidakis, Haris; Hyatt-Denesik, Dylan; Sanita, Laura
作者单位：Eindhoven University of Technology
摘要：Many network design problems deal with the design of low-cost networks that are resilient to the failure of their elements (such as nodes or links). One such problem is Connectivity Augmentation, with the goal of cheaply increasing the (edge- or node)connectivity of a given network from a value k to k + 1. The problem is NP-hard for k >= 1, and the most studied setting focuses on the case of edge-connectivity with k = 1. In this work, we give a 1.892-approximation algorithm for the NP-hard pro...
-
作者：Faenza, Yuri; Zhang, Xuan
作者单位：Columbia University
摘要：Birkhoff's representation theorem (Birkhoff, Duke Math J 3(3):443-454, 1937) defines a bijection between elements of a distributive lattice and the family of upper sets of an associated poset. Although not used explicitly, this result is at the backbone of the combinatorial algorithm by Irving et al. (J ACM 34(3):532-543, 1987) for maximizing a linear function over the set of stable matchings in Gale and Shapley's stable marriage model (Gale and Shapley, Am Math Monthly 69(1):9-15 1962). In th...
-
作者：Dzahini, Kwassi Joseph; Kokkolaras, Michael; Le Digabel, Sebastien
作者单位：Universite de Montreal; Polytechnique Montreal; Universite de Montreal; Polytechnique Montreal; Universite de Montreal; McGill University
摘要：This work introduces the StoMADS-PB algorithm for constrained stochastic blackbox optimization, which is an extension of the mesh adaptive direct-search (MADS) method originally developed for deterministic blackbox optimization under general constraints. The values of the objective and constraint functions are provided by a noisy blackbox, i.e., they can only be computed with random noise whose distribution is unknown. As in MADS, constraint violations are aggregated into a single constraint v...
-
作者：Guenin, Bertrand; Heo, Cheolwon
作者单位：University of Waterloo
摘要：Even-cycle matroids are elementary lifts of graphic matroids and even-cut matroids are elementary lifts of cographic matroids. We present a polynomial algorithm to check if a binary matroid is an even-cycle matroid and we present a polynomial algorithm to check if a binary matroid is an even-cut matroid. These two algorithms rely on a polynomial algorithm (to be described in a pair of follow-up papers) to check if a binary matroid is pinch-graphic.
-
作者：Dey, Santanu S.; Molinaro, Marco; Wang, Guanyi
作者单位：University System of Georgia; Georgia Institute of Technology; Pontificia Universidade Catolica do Rio de Janeiro
摘要：Sparse principal component analysis with global support (SPCAgs), is the problem of finding the top-r leading principal components such that all these principal components are linear combinations of a common subset of at most k variables. SPCAgs is a popular dimension reduction tool in statistics that enhances interpretability compared to regular principal component analysis (PCA). Methods for solving SPCAgs in the literature are either greedy heuristics (in the special case of r = 1) with gua...
-
作者：Altschuler, Jason M.; Parrilo, Pablo A.
作者单位：Massachusetts Institute of Technology (MIT)
摘要：We revisit Matrix Balancing, a pre-conditioning task used ubiquitously for computing eigenvalues and matrix exponentials. Since 1960, Osborne's algorithm has been the practitioners' algorithm of choice, and is now implemented in most numerical software packages. However, the theoretical properties of Osborne's algorithm are not well understood. Here, we show that a simple random variant of Osborne's algorithm converges in near-linear time in the input sparsity. Specifically, it balances K is a...
-
作者：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...
