Search

We consider the following node-capacitated network design problem. The input is an undirected graph, a set of demands, uniform node capacity, and arbitrary node costs. The goal is to find a minimum node-cost subgraph that supports all demands concurrently subject to the node capacities. We consider both single- and multicommodity demands and provide the first polylogarithmic approximation guarantees. For single-commodity demands (i.e., all request pairs have the same sink node), we obtain an O(log²n) approximation to the cost with an O(log³n) factor violation in node capacities. For multicommodity demands, we obtain an O(log4n) approximation to the cost with an O(log10n) factor violation in node capacities. We use a variety of techniques, including single-sink confluent flows, low-load set cover, random sampling, and cut-sparsification. We also develop new techniques for clustering multicommodity demands into (nearly) node-disjoint clusters, which may be of independent interest. Moreover, this network design problem has applications to energy-efficient virtual circuit routing. In this setting, there is a network of routers that are speed scalable and that may be shut down when idle. We assume the standard model for power: the power consumed by a router with load (speed) s is \sigma + s\alpha, where \sigma is the static power and the exponent \alpha > 1. We obtain the first polylogarithmic approximation algorithms for this problem when speed-scaling occurs on nodes of a network. [ABSTRACT FROM AUTHOR]

We abstract and study reachability preservers, a graph-theoretic primitive that has been implicit in prior work on network design. Given a directed graph G=(V,E) and a set of demand pairs P⊆VxV, a reachability preserver is a sparse subgraph H that preserves reachability between all demand pairs. Our first contribution is a series of extremal bounds on the size of reachability preservers. Our main result states that, for an n-node graph and demand pairs of the form P⊆SxV for a small node subset S, there is always a reachability preserver on O(n+√n/P//S/) edges. We additionally give a lower bound construction demonstrating that this upper bound characterizes the settings in which O(n) size reachability preservers are generally possible, in a large range of parameters. The second contribution of this paper is a new connection between extremal graph sparsification results and classical Steiner Network Design problems. Surprisingly, prior to this work, the osmosis of techniques between these two fields had been superficial. This allows us to improve the state of the art approximation algorithms for the most basic Steiner-type problem in directed graphs from the O(n0.6+ε) of Chlamatac, et al. [Approximating spanners and directed steiner forest: Upper and lower bounds, in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 2017, pp. 534-443] (n4/7+ε). [ABSTRACT FROM AUTHOR]

Randomized matrix algorithms have become workhorse tools in scientific computing and machine learning. To use these algorithms safely in applications, they should be coupled with posterior error estimates to assess the quality of the output. To meet this need, this paper proposes two diagnostics: a leave-one-out error estimator for randomized low-rank approximations and a jackknife resampling method to estimate the variance of the output of a randomized matrix computation. Both of these diagnostics are rapid to compute for randomized low-rank approximation algorithms such as the randomized SVD and randomized Nystr\"om approximation, and they provide useful information that can be used to assess the quality of the computed output and guide algorithmic parameter choices. [ABSTRACT FROM AUTHOR]

The present work is devoted to the eigenvalue asymptotic expansion of the Toeplitz matrix Tn(a), whose generating function a is complex-valued and has a power singularity at one point. As a consequence, Tn(a) is non-Hermitian and we know that in this setting, the eigenvalue computation is a nontrivial task for large sizes. First we follow the work of Bogoya, Böttcher, Grudsky, and Maximenko and deduce a complete asymptotic expansion for the eigenvalues. In a second step, we apply matrixless algorithms, in the spirit of the work by Ekström, Furci, Garoni, Serra-Capizzano et al., for computing those eigenvalues. Since the inner and extreme eigenvalues have different asymptotic behaviors, we worked on them independently and combined the results to produce a high precision global numerical and matrixless algorithm. The numerical results are very precise, and the computational cost of the proposed algorithms is independent of the size of the considered matrices for each eigenvalue, which implies a linear cost when the entire spectrum is computed. From the viewpoint of real-world applications, we emphasize that the class under consideration includes the matrices stemming from the numerical approximation of fractional diffusion equations. In the final section a concise discussion on the matter and a few open problems are presented. [ABSTRACT FROM AUTHOR]

Given a metric space \scrM = (X, γ), a weighted graph G over X is a metric t-spanner of scrM if for every u, v \in X, γ(u, v) \leq γG(u, v) \leq t \cdot γ (u, v), where γ G is the shortest path metric in G. In this paper, we construct spanners for finite sets in metric spaces in the online setting. Here, we are given a sequence of points (s1,. . ., sn), where the points are presented one at a time (i.e., after i steps, we see Si = \{ s1, . . ., si\}). The algorithm is allowed to add edges to the spanner when a new point arrives; however, it is not allowed to remove any edge from the spanner. The goal is to maintain a t-spanner Gi for Si for all i, while minimizing the number of edges, and their total weight. We construct online (1+ε)-spanners in the Euclidean d-space, (2k 1)(1+ε)-spanners for general metrics, and (2 + ε)-spanners for ultrametrics. Most notably, in the Euclidean plane, we construct a (1 + ε)-spanner with competitive ratio O(\varepsilon 3/2 log n 1 log n), bypassing the classic lower bound (ε 2) for lightness, which compares the weight of the spanner to that of the minimum spanning tree. [ABSTRACT FROM AUTHOR]

Since the seminal result of Karger, Motwani, and Sudan, algorithms for approximate 3-coloring have primarily centered around rounding the solution to a Semidefinite Program. However, it is likely that important combinatorial or algebraic insights are needed in order to break the no(1) threshold. One way to develop new understanding in graph coloring is to study special subclasses of graphs. For instance, Blum studied the 3-coloring of random graphs, and Arora and Ge studied the 3-coloring of graphs with low threshold-rank. In this work, we study graphs that arise from a tensor product, which appear to be novel instances of the 3-coloring problem. We consider graphs of the form H = (V,E) with V = V (K3 G) and E = E(K3 G) s E, where E E(K3 G) is any edge set such that no vertex has more than an -fraction of its edges in E. We show that one can construct H = K3 \times G with V (H) = V (H) that is close to H. For arbitrary G, H satisfies | E(H)Δ E H)| O(\epsilon | E(H)|). Additionally, when G is a mild expander, we provide a 3-coloring for H in polynomial time. These results partially generalize an exact tensor factorization algorithm of Imrich. On the other hand, without any assumptions on G, we show that it is NP-hard to 3-color H. [ABSTRACT FROM AUTHOR]

Let P be a set of points in Rd, where each point p ∈ P has an associated transmission range, denoted (p). The range assignment induces a directed communication graph Gp (P) on P, which contains an edge (p, q) iff | pq| (p). In the broadcast range-assignment problem, the goal is to assign the ranges such that (P) contains an arborescence rooted at a designated root node and the costΣp∈ P(p)² of the assignment is minimized. We study the dynamic version of this problem. In particular, we study trade-offs between the stability of the solution-the number of ranges that are modified when a point is inserted into or deleted from P-and its approximation ratio. To this end we study k-stable algorithms, which are algorithms that modify the range of at most k points when they update the solution. We also introduce the concept of a stable approximation scheme, or SAS for short. A SAS is an update algorithm \mathrm{A}\mathrm{L}\mathrm{G} that, for any given fixed parameter ε >0, is kε-stable and that maintains a solution with approximation ratio 1 + \ε, where the stability parameter k(\varepsilon) only depends on ε and not on the size of P. We study such trade-offs in three settings. (1) For the problem in R¹, we present a SAS with kε = O(1/ε. Furthermore, we prove that this is tight in the worst case: any SAS for the problem must have kε =ε (1ε). We also present 1-, 2-, and 3-stable algorithms with constant approximation ratio. (2) For the problem in S1 (that is, when the underlying space is a circle) we prove that no SAS exists. This is in spite of the fact that, for the static problem in S1, we prove that an optimal solution can always be obtained by cutting the circle at an appropriate point and solving the resulting problem in R¹. (3) For the problem in R2, we also prove that no SAS exists, and we present a O(1)-stable O(1)-approximation algorithm. Most results γ generalize to the setting where, for any given constant α > 1, the range-assignment cost is pΣ (p)∈α. [ABSTRACT FROM AUTHOR]

We consider classes of objective functions of cardinality-constrained maximization problems for which the greedy algorithm guarantees a constant approximation. We propose the new class of γ -β -augmentable functions and prove that it encompasses several important subclasses, such as functions of bounded submodularity ratio, \alpha -augmentable functions, and weighted rank functions of an independence system of bounded rank quotient-as well as additional objective functions for which the greedy algorithm yields an approximation. For this general class of functions, we show a tight bound of α/γeα/eα-1 \mathrm{e}α 1 on the approximation ratio of the greedy algorithm that tightly interpolates between bounds from the literature for functions of bounded submodularity ratio and for α -augmentable functions. In particular, as a by-product, we close a gap in [A. Bernstein et al., Math. Program., 191 (2022), pp. 953--979] by obtaining a tight lower bound for \alpha -augmentable functions for all \α 1. For weighted rank functions of independence systems, our tight bound becomes α, which recovers the known bound of 1/q for independence systems of rank quotient at least q. [ABSTRACT FROM AUTHOR]

We consider a selection problem with stochastic probing. There is a set of items whose values are drawn from independent distributions. The distributions are known in advance. Each item can be tested repeatedly. Each test reduces the uncertainty about the realization of its value. We study a testing model, where the first test reveals whether the realized value is smaller or larger than the c-quantile of the underlying distribution of some constant c \in (0, 1). Subsequent tests allow us to further narrow down the interval in which the realization is located. There is a limited number of possible tests, and our goal is to design near-optimal testing strategies that allow us to maximize the expected value of the chosen item. We study both identical and nonidentical distributions and develop polynomial-time algorithms with constant approximation factors in both scenarios. [ABSTRACT FROM AUTHOR]

In the weighted flow-time problem on a single machine, we are given a set of n jobs, where each job has a processing requirement pj, release date rj, and weight wj. The goal is to find a preemptive schedule which minimizes the sum of weighted flow-time of jobs, where the flow-time of a job is the difference between its completion time and its released date. We give the first pseudopolynomial time constant approximation algorithm for this problem. The algorithm also extends directly to the problem of minimizing the lp norm of weighted flow-times. The running time of our algorithm is polynomial in n, the number of jobs, and P, which is the ratio of the largest to the smallest processing requirement of a job. Our algorithm relies on a novel reduction of this problem to a generalization of the multicut problem on trees, which we call the Demand MultiCut problem. Even though we do not give a constant factor approximation algorithm for the Demand MultiCut problem on trees, we show that the specific instances of Demand MultiCut obtained by reduction from weighted flow-time problem instances have more structure in them, and we are able to employ techniques based on dynamic programming. Our dynamic programming algorithm relies on showing that there are near optimal solutions which have nice smoothness properties, and we exploit these properties to reduce the size of the dynamic programming table. [ABSTRACT FROM AUTHOR]

Among various variants of the traveling salesman problem (TSP), the s-t-path graph TSP has the special feature that we know the exact integrality ratio, 3 2, and an approximation algorithm matching this ratio. In this paper, we go below this threshold: we devise a polynomialtime algorithm for the s-t-path graph TSP with approximation ratio 1.497. Our algorithm can be viewed as a refinement of the 3 2 -approximation algorithm in [A. SebH o and J. Vygen, Combinatorica, 34 (2014), pp. 597--629], but we introduce several completely new techniques. These include a new type of ear-decomposition, an enhanced ear induction that reveals a novel connection to matroid union, a stronger lower bound, and a reduction of general instances to instances in which s and t have small distance (which works for general metrics). [ABSTRACT FROM AUTHOR]

In the dynamic minimum set cover problem, the challenge is to minimize the update time while guaranteeing a close-to-optimal min\{ O(log n), f\} approximation factor. (Throughout, n, m, f, and C are parameters denoting the maximum number of elements, the number of sets, the frequency, and the cost range.) In the high-frequency range, when f = \Omega (log n), this was achieved by a deterministic O(log n)-approximation algorithm with O(f log n) amortized update time by Gupta et al. [Online and dynamic algorithms for set cover, in Proceedings STOC 2017, ACM, pp. 537--550]. In this paper we consider the low-frequency range, when f =O(log n), and obtain deterministic algorithms with a (1 + \epsilon)f-approximation ratio and the following guarantees on the update time. (1) O((f/\epsilon) \cdot log(Cn)) amortized update time: Prior to our work, the best approximation ratio guaranteed by deterministic algorithms was O(f2) of Bhattacharya, Henzinger, and Italiano [Design of dynamic algorithms via primal-dual method, in Proceedings ICALP 2015, Springer, pp. 206--218]. In contrast, the only result with O(f)-approximation was that of Abboud et al. [Dynamic set cover: Improved algorithms and lower bounds, in Proceedings STOC 2019, ACM, pp. 114--125], who designed a randomized (1+\epsilon)f-approximation algorithm with O((f2/\epsilon) \cdot log n) amortized update time. (2) O \bigl(f2/\epsilon 3 + (f/\epsilon 2) \cdot logC \bigr) amortized update time: This result improves the above update time bound for most values of f in the low-frequency range, i.e., f =o(log n). It is also the first result that is independent of m and n. It subsumes the constant amortized update time of Bhattacharya and Kulkarni [Deterministically maintaining a (2 + \epsilon)-approximate minimum vertex cover in O(1/\epsilon 2) amortized update time, in Proceedings SODA 2019, SIAM, pp. 1872--1885] for unweighted dynamic vertex cover (i.e., when f = 2 and C = 1). (3) O((f/\epsilon 3) \cdot log2(Cn)) worst-case update time: No nontrivial worst-case update time was previously known for the dynamic set cover problem. Our bound subsumes and improves by a logarithmic factor the O(log3 n/\sansp \sanso \sansl \sansy (\epsilon)) worst-case update time for the unweighted dynamic vertex cover problem (i.e., when f = 2 and C = 1) of Bhattacharya, Henzinger, and Nanongkai [Fully dynamic approximate maximum matching and minimum vertex cover in O(log3)n worst case update time, in Proceedings SODA 2017, SIAM, pp. 470--489]. We achieve our results via the primal-dual approach, by maintaining a fractional packing solution as a dual certificate. Prior work in dynamic algorithms that employs the primal-dual approach uses a local update scheme that maintains relaxed complementary slackness conditions for every set. For our first result we use instead a global update scheme that does not always maintain complementary slackness conditions. For our second result we combine the global and the local update schema. To achieve our third result we use a hierarchy of background schedulers. It is an interesting open question whether this background scheduler technique can also be used to transform algorithms with amortized running time bounds into algorithms with worst-case running time bounds. [ABSTRACT FROM AUTHOR]

Surrogate models can reduce computational costs for multivariable functions with an unknown internal structure (black boxes). In a discrete formulation, surrogate modeling is equivalent to restoring a multidimensional array (tensor) from a small part of its elements. The alternating least squares (ALS) algorithm in the tensor train (TT) format is a widely used approach to effectively solve this problem in the case of nonadaptive tensor recovery from a given training set (i.e., tensor completion problem). TT-ALS allows obtaining a low-parametric representation of the tensor, which is free from the curse of dimensionality and can be used for fast computation of the values at arbitrary tensor indices or efficient implementation of algebra operations with the black box (integration, etc.). However, to obtain high accuracy in the presence of restrictions on the size of the train data, a good choice of initial approximation is essential. In this work, we construct the ANOVA representation in the TT-format and use it as an initial approximation for the TT-ALS algorithm. The performed numerical computations for a number of multidimensional model problems, including the parametric partial differential equation, demonstrate a significant advantage of our approach for the commonly used random initial approximation. For all considered model problems we obtained an increase in accuracy by at least an order of magnitude with the same number of requests to the black box. The proposed approach is very general and can be applied in a wide class of real-world surrogate modeling and machine learning problems. [ABSTRACT FROM AUTHOR]

We consider min-max-min optimization with smooth and strongly convex objectives. Our motivation for studying this class of problems stems from its connection to the κ-center problem and the growing literature on min-max-min robust optimization. In particular, the considered class of problems nontrivially generalizes the Euclidean κ-center problem in the sense that distances in this more general setting do not necessarily satisfy metric properties. We present a 9κ-approximation algorithm (whereκ is the maximum condition number of the functions involved) that generalizes a simple greedy 2-approximation algorithm for the classical κ-center problem. We show that for any choice ofκ, there is an instance with a condition number ofκ per which our algorithm yields a (4κ+ 4κ + 1)-approximation guarantee, implying that our analysis is tight whenκ=1. Finally, we compare the computational performance of our approximation algorithm with an exact mixed integer linear programming approach. [ABSTRACT FROM AUTHOR]

The matrix spectral norm and nuclear norm appear in enormous applications. The generalization of these norms to higher-order tensors is becoming increasingly important, but unfortunately they are NP-hard to compute or even approximate. Although the two norms are dual to each other, the best-known approximation bound achieved by polynomial-time algorithms for the tensor nuclear norm is worse than that for the tensor spectral norm. In this paper, we bridge this gap by proposing deterministic algorithms with the best bound for both tensor norms. Our methods not only improve the approximation bound for the nuclear norm but also are data independent and easily implementable compared to existing approximation methods for the tensor spectral norm. The main idea is to construct a selection of unit vectors that can approximately represent the unit sphere, in other words, a collection of spherical caps to cover the sphere. For this purpose, we explicitly construct several collections of spherical caps for sphere covering with adjustable parameters for different levels of approximations and cardinalities. These readily available constructions are of independent interest, as they provide a powerful tool for various decision-making problems on spheres and related problems. We believe the ideas of constructions and the applications to approximate tensor norms can be useful to tackle optimization problems over other sets, such as the binary hypercube. [ABSTRACT FROM AUTHOR]

Modern applications of graph algorithms often involve the use of the output sets (usually, a subset of edges or vertices of the input graph) as inputs to other algorithms. Since the input graphs of interest are large and dynamic, it is desirable for an algorithm's output to not change drastically when a few random edges are removed from the input graph, so as to prevent issues in postprocessing. Alternately, having such a guarantee also means that one can revise the solution obtained by running the algorithm on the original graph in just a few places in order to obtain a solution for the new graph. We formalize this feature by introducing the notion of average sensitivity of graph algorithms, which is the average earth mover's distance between the output distributions of an algorithm on a graph and its subgraph obtained by removing an edge, where the average is over the edges removed and the distance between two outputs is the Hamming distance. In this work, we initiate a systematic study of average sensitivity of graph algorithms. After deriving basic properties of average sensitivity such as composition, we provide efficient approximation algorithms with low average sensitivities for concrete graph problems, including the minimum spanning forest problem, the global minimum cut problem, the minimum s-t cut problem, and the maximum matching problem. In addition, we prove that the average sensitivity of our global minimum cut algorithm is almost optimal, by showing a nearly matching lower bound. We also show that every algorithm for the 2-coloring problem has average sensitivity linear in the number of vertices. One of the main ideas involved in designing our algorithms with low average sensitivity is the following fact: if the presence of a vertex or an edge in the solution output by an algorithm can be decided locally, then the algorithm has a low average sensitivity, allowing us to reuse the analyses of known subline artime algorithms and local computation algorithms. Using this fact in conjunction with our average sensitivity lower bound for 2-coloring, we show that every local computation algorithm for 2-coloring has query complexity linear in the number of vertices, thereby answering an open question. [ABSTRACT FROM AUTHOR]

Motivated by an application in cancer genomics, Hajirasouliha and Raphael [Proceedings of the 14th International Workshop on Algorithms in Bioinformatics, 2014, pp. 354-367] proposed the split-row problem (SR). In this problem, an m\times n binary matrix M is given. A split-row operation on M is defined as replacing a row r by k > 1 rows r(1), r(2), . . ., r(k) whose bitwise OR is equal to r. The cost of the operation is the number of additional rows induced, that is, k 1. The goal is to find a sequence of split-row operations that transforms M into a matrix corresponding to a perfect phylogeny and the total cost is minimized. Recently, Hujdurovi\'c et al. [ACM Trans. Algorithms, 14 (2018), 26] proved the APX-hardness of SR and presented efficient exact and approximation algorithms. The parameterized study of SR was left as a direction for future work. Let\varepsilon (M) denote the minimum total cost. This paper gives an O*(2min(n,2x(M))-time exact algorithm for SR. This result indicates that SR is fixed-parameter tractable when parameterized by E (M). In addition, in the worst case, our algorithm requires O* (2n) time, significantly improving the previous upper bound of O\ast (nn). Hujdurovi\'c et al.'s exact algorithm can be modified to solve a variant of SR, called the distinct split-row problem (DSR). Our algorithm can be adapted to this variant as well. In addition, our algorithms can be extended to solve SR and DSR with the following additional constraint: only the rows in a given subset are allowed to be split. [ABSTRACT FROM AUTHOR]

Approximating the partition function of the ferromagnetic Ising model with general external fields is known to be\#BIS-hard in the worst case, even for bounded-degree graphs, and it is widely believed that no polynomial-time approximation scheme exists. This motivates an averagecase question: are there classes of instances for which polynomial-time approximation schemes exist? We investigate this question for the random field Ising model on graphs with maximum degree\Delta. We establish the existence of fully polynomial-time approximation schemes and samplers with high probability over the random fields if the external fields are independent and identically distributed Gaussians with variance larger than a constant depending only on the inverse temperature and\Delta. Our methods work more generally for external fields that are large in absolute value with high probability. The main challenge is that such a hypothesis does not rule out the existence of a positive density of vertices at which the external field is small. These regions, which may have connected components of size\Theta (log n), are a barrier to algorithms based on establishing zero-free regions of partition functions and cause worst-case analyses of Glauber dynamics to fail. The analysis of our algorithm is based on percolation on a self-avoiding walk tree. [ABSTRACT FROM AUTHOR]

The basic goal of survivable network design is to build a cheap network that maintains the connectivity between given sets of nodes despite the failure of a few edges/nodes. The connectivity augmentation problem (CAP) is arguably one of the most basic problems in this area: given a k(-edge)-connected graph G and a set of extra edges (links), select a minimum cardinality subset A of links such that adding A to G increases its edge connectivity to k+1. Intuitively, one wants to make an existing network more reliable by augmenting it with extra edges. The best known approximation factor for this NP-hard problem is 2, and this can be achieved with multiple approaches (the first such result is in [G. N. Frederickson and J\'aj\'a, SIAM J. Comput., 10 (1981), pp. 270--283]. It is known [E. A. Dinitz, A. V. Karzanov, and M. V. Lomonosov, Studies in Discrete Optimization, Nauka, Moscow, 1976, pp. 290--306] that CAP can be reduced to the case k = 1, also known as the tree augmentation problem (TAP) for odd k, and to the case k = 2, also known as the cactus augmentation problem (CacAP) for even k. Prior to the conference version of this paper [J. Byrka, F. Grandoni, and A. Jabal Ameli, STOC'20, ACM, New York, 2020, pp. 815--825], several better than 2 approximation algorithms were known for TAP, culminating with a recent 1.458 approximation [F. Grandoni, C. Kalaitzis, and R. Zenklusen, STOC'18, ACM, New York, 1918, pp. 632--645]. However, for CacAP the best known approximation was 2. In this paper we breach the 2 approximation barrier for CacAP, hence, for CAP, by presenting a polynomial-time 2 ln(4) 967 1120 + \varepsilon < 1.91 approximation. From a technical point of view, our approach deviates quite substantially from previous work. In particular, the better-than-2 approximation algorithms for TAP either exploit greedy-style algorithms or are based on rounding carefully designed LPs. We instead use a reduction to the Steiner tree problem which was previously used in parameterized algorithms [Basavaraju et al., ICALP'14, Springer, Berlin, 2014, pp. 800--811]. This reduction is not approximation preserving, and using the current best approximation factor for a Steiner tree [Byrka et al., J. ACM, 60 (2013), 6] as a black box would not be good enough to improve on 2. To achieve the latter goal, we "open the box" and exploit the specific properties of the instances of a Steiner tree arising from CacAP. In our opinion this connection between approximation algorithms for survivable network design and Steiner-type problems is interesting, and might lead to other results in the area. [ABSTRACT FROM AUTHOR]

We study the Generalized Min Sum Set Cover (GMSSC) problem, wherein given a collection of hyperedges E with arbitrary covering requirements { ke Z + : e Ⲉ E}, the goal is to find an ordering of the vertices to minimize the total cover time of the hyperedges; a hyperedge e is considered covered by the first time when ke and many of its vertices appear in the ordering. We give a 4.642 approximation algorithm for GMSSC, coming close to the best possible bound of 4, already for the classical special case (with all ke = 1) of Min Sum Set Cover (MSSC) studied by Feige, Lovász, and Tetali, and improving upon the previous best known bound of 12.4 due to Im, Sviridenko, and van der Zwaan. Our algorithm is based on transforming the LP solution by a suitable kernel and applying randomized rounding. As part of the analysis of our algorithm, we also derive an inequality on the lower tail of a sum of independent Bernoulli random variables, which might be of independent interest and broader utility. Min Sum Vertex Cover (MSVC) is a well-known special case of MSSC in which the input hypergraph is a graph (i.e., | e| = 2) and ke = 1 for every edge e E. We give a 16/9 ≃ 1.778 approximation for MSVC and show a matching integrality gap for the natural LP relaxation. This improves upon the previous best 1.999946 approximation of Barenholz, Feige, and Peleg. Finally, we revisit MSSC and consider the lp norm of cover-time of the hyperedges. Using a dual fitting argument, we show that the natural greedy algorithm achieves tight, up to NP-hardness, approximation guarantees of (p + 1)1+1/p for all p ≥ 1, giving another proof of the result of Golovin, Gupta, Kumar, and Tangwongsan, and showing its tightness up to NP-hardness. For p = 1, this gives yet another proof of the 4 approximation for MSSC. [ABSTRACT FROM AUTHOR]

In the directed Steiner tree (DST) problem, we are given an n-vertex directed edgeweighted graph, a root r, and a collection of k terminal nodes. Our goal is to find a minimum-cost subgraph that contains a directed path from r to every terminal. We present an O(log² k/ log log k)- approximation algorithm for DST that runs in quasi-polynomial time, i.e., in time n poly log(k) . By assuming the projection game conjecture and NP ¢n0<ε<1 ZPTIME(2nε ) and adjusting the parameters in the hardness result of [Halperin and Krauthgamer, Polylogarithmic inapproximability, in Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003, pp. 585--594], we show the matching lower bound of Ω (log² k/ log log k) for the class of quasi-polynomial time algorithms, meaning that our approximation ratio is asymptotically the best possible. Our algorithm is proceeded by reducing DST to an intermediate problem, namely, the group Steiner tree on trees with dependency constraint problem, which we approximate using the framework developed by [Rothvo{\ss}, Directed Steiner Tree and the Lasserre Hierarchy, preprint, arxiv:1111.5473, 2011] and [Friggstad et al., Linear programming hierarchies suffice for directed Steiner tree, in Proceedings of the 17th Annual Conference on Integer Programming and Combinatorial Optimization, 2014, pp. 285--296]. [ABSTRACT FROM AUTHOR]

Abstract. In the distributed all-pairs shortest paths problem, every node in the weighted undirected distributed network (the CONGEST model) needs to know the distance from every other node using least number of communication rounds (typically called time complexity). The problem admits a (1 + (1))-approximation 9(n)-time algorithm and a nearly tight 12(n) lower bound [D. Nanongkai, STOC'14, ACM, New York, 2014, pp. 565-573; C. Lenzen and B. Patt-Shamir, PODC'15, ACM, New York, 2015, pp. 153-162]. (9, 0 and n hide polylogarithmic factors. Note that the lower bounds also hold even in the unweighted case and in the weighted case with polynomial approximation ratios (C. Lenzen and D. Peleg, PODC, ACM, New York, 2013, pp. 375-382; S. Holzer and R. Wattenofer, PODC, ACM, New York, 2012, pp. 355-364; D. Peleg, L. Roditty, and E. Tal, ICALP, Springer, Berlin, 2012, pp. 660-672; D. Nanongkai, STOC, ACM, New York, 2014, pp. 565-573-672). For the exact case, Elkin [STOC'17, ACM, New York, 2017, pp. 757-790] presented an 0(n5/3 log2/3 n) time bound, which was later improved to O(n5/4) [C.-C. Huang, D. Nanongkai, T. Saranurak, FOCS'17, IEEE Computer Society, Los Alamitos, CA, 2017, pp. 168-179]. It was shown that any superlinear lower bound (in n) requires a new technique [K. Censor-Hillel, S. Khoury, A. Paz, DISC'17, LIPIcs Leibniz Int. Proc. Inform., Vol. 91, Schloss-Dagstuhl, Wadern, Germany, 2017, 10], but otherwise it remained widely open whether there exists a O(n)-time algorithm for the exact case, which would match the best possible approximation algorithm. This paper resolves this question positively: we present a randomized (Las Vegas) 0(n)-time algorithm, matching the lower bound up to polylogarithmic factors. Like the previous 0(n5/4) bound, our result works for directed graphs with zero (and even negative) edge weights. In addition to the improved running time, our algorithm works in a more general setting than that required by the previous 0(n5/4) bound; in our setting (i) the communication is only along edge directions (as opposed to bidirectional), and (ii) edge weights are arbitrary (as opposed to integers in {1, 2, ..., poly(n)}). As far as we know, ours is the first o(n²) algorithm that only requires unidirectional communication. For arbitrary weights, the previous state-of-the-art required 0(n4/3) time [U. Agarwal and V. Ramachandran, IPDPS 2019, IEEE Computer Society, Los Alamitos, CA, 2019, and SPAA 2020, ACM, New York, 2020, pp. 11-21]. Our algorithm is extremely simple and relies on a new technique called random filtered broadcast. Given any sets of nodes A, B C V and assuming that every b E B knows all distances from nodes in A, and every node v E V knows all distances from nodes in B, we want every v E V to know DistThroughB (a, v) = minbEB dist(a, b) + dist(b, v) for every a E A. Previous works typically solve this problem by broadcasting all knowledge of every b E B, causing superlinear edge congestion and time. We show a randomized algorithm that can reduce edge congestions and thus solve this problem in 0(n) expected time. [ABSTRACT FROM AUTHOR]

We analyze a new algorithm for the finite element approximation of a family of eigenvalue problems for the curl operator that includes, in particular, the approximation of the helicity of a bounded domain. It exploits a tree-cotree decomposition of the graph relating the degrees of freedom of the Lagrangian finite elements and those of the first family of N\'ed\'elec finite elements to reduce significantly the dimension of the algebraic eigenvalue problem to be solved. The algorithm is well adapted to domains of general topology. Numerical experiments, including a not simply connected domain with a not connected boundary, are presented in order to assess the performance and generality of the method. [ABSTRACT FROM AUTHOR]

The tensor-train (TT) format is a highly compact low-rank representation for highdimensional tensors. TT is particularly useful when representing approximations to the solutions of certain types of parametrized partial differential equations. For many of these problems, computing the solution explicitly would require an infeasible amount of memory and computational time. While the TT format makes these problems tractable, iterative techniques for solving the PDEs must be adapted to perform arithmetic while maintaining the implicit structure. The fundamental operation used to maintain feasible memory and computational time is called rounding, which truncates the internal ranks of a tensor already in TT format. We propose several randomized algorithms for this task that are generalizations of randomized low-rank matrix approximation algorithms and provide significant reduction in computation compared to deterministic TT-rounding algorithms. Randomization is particularly effective in the case of rounding a sum of TT-tensors (where we observe 20\times speedup), which is the bottleneck computation in the adaptation of GMRES to vectors in TT format. We present the randomized algorithms and compare their empirical accuracy and computational time with deterministic alternatives. [ABSTRACT FROM AUTHOR]

We study geometric duality for convex vector optimization problems. For a primal problem with a q-dimensional objective space, we formulate a dual problem with a (q+1)-dimensional objective space. Consequently, different from an existing approach, the geometric dual problem does not depend on a fixed direction parameter, and the resulting dual image is a convex cone. We prove a one-to-one correspondence between certain faces of the primal and dual images. In addition, we show that a polyhedral approximation for one image gives rise to a polyhedral approximation for the other. Based on this, we propose a geometric dual algorithm which solves the primal and dual problems simultaneously and is free of direction-biasedness. We also modify an existing direction-free primal algorithm in such a way that it solves the dual problem as well. We test the performance of the algorithms for randomly generated problem instances by using the so-called primal error and hypervolume indicator as performance measures. [ABSTRACT FROM AUTHOR]

We study the problem of computing the p q norm of a matrix A ∈ Rm×n, defined as ∣∣j4∣∣p-g = maxx∈Rn{0}'.||Ax|q/||x|p This problem generalizes the spectral norm of a matrix (p = q = 2) and the Grothendieck problem (p = ∞, q = 1) and has been widely studied in various regimes. When p ≥ q, the problem exhibits a dichotomy: constant factor approximation algorithms are known if 2 ∈ [g,p], and the problem is hard to approximate within almost polynomial factors when 2 [g,p]. The regime when p < q, known as Hypercontractive norms, is particularly significant for various applications but much less well understood. The case with p = 2 and q > 2 was studied by Barak et al. [Proceedings of the 4Ath Annual ACM Symposium on Theory of Computing, 2012, pp. 307--326], who gave subexponential algorithms for a promise version of the problem (which captures small-set expansion) and also proved hardness of approximation results based on the exponential time hypothesis. However, no NP-hardness of approximation is known for these problems for any p < q. We prove the first NP-hardness result (under randomized reductions) for approximating hypercontractive norms. We show that for any 1 < p < q < ∞ with 2 [p, g], ∣∣√4∣∣p--q is hard to approximate within 2°(log n)1-x) assuming NP g BPTIME(21log n A-). En rθute to the above result, we also prove almost tight results for the case when p > q with 2 ∈ [q, p]. [ABSTRACT FROM AUTHOR]

The terminal backup problems ([E. Anshelevich and A. Karagiozova, SIAM J. Comput., 40 (2011), pp. 678--708]) form a class of network design problems: Given an undirected graph with a requirement on terminals, the goal is to find a minimum-cost subgraph satisfying the connectivity requirement. The node-connectivity terminal backup problem requires a terminal to connect other terminals with a number of node-disjoint paths. This problem is not known whether is NP-hard or tractable. Fukunaga [SIAM J. Discrete Math., 30 (2016), pp. 777--800] gave a 4/3-approximation algorithm based on an LP-rounding scheme using a general LP-solver. In this paper, we develop a combinatorial algorithm for the relaxed LP to find a half-integral optimal solution in O(mlog(n-A · MF(/cn,m T/c2n)) time, where n is the number of nodes, m is the number of edges, k is the number of terminals, A is the maximum edge-cost, U is the maximum edge-capacity, and MF(nz,mz) is the time complexity of a max-flow algorithm in a network with nz nodes and m' edges. The algorithm implies that the 4/3-approximation algorithm for the node-connectivity terminal backup problem is also efficiently implemented. For the design of algorithm, we explore a connection between the node-connectivity terminal backup problem and a new type of a multiflow, which is called a separately capacitated multiflow. We show a min-max theorem which extends the Lovasz-Cherkassky theorem to the node-capacity setting. Our results build on discrete convexity in the node-connectivity terminal backup problem. [ABSTRACT FROM AUTHOR]

We present a 5/3-approximation algorithm for the matching augmentation problem (MAP): given a multigraph 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. A 7/4-approximation algorithm for the same problem was presented recently; see Cheriyan et al. [Math. Program., 182 (2020), pp. 315--354]. Our improvement is based on new algorithmic techniques, and some of these may lead to advances on related problems. [ABSTRACT FROM AUTHOR]

Graph sparsification underlies a large number of algorithms, ranging from approximation algorithms for cut problems to solvers for linear systems in the graph Laplacian. In its strongest form, "spectral sparsification" reduces the number of edges to near-linear in the number of nodes, while approximately preserving the cut and spectral structure of the graph. In this work we demonstrate a polynomial quantum speedup for spectral sparsification and many of its applications. In particular, we give a quantum algorithm that, given a weighted graph with n nodes and m edges, outputs a classical description of an ϵ-spectral sparsifier in sublinear time Õ(√mn/ϵ). This contrasts with the optimal classical complexity Õ(m). We also prove that our quantum algorithm is optimal up to polylog-factors. The algorithm builds on a string of existing results on sparsification, graph spanners, quantum algorithms for shortest paths, and efficient constructions for k-wise independent random strings. Our algorithm implies a quantum speedup for solving Laplacian systems and for approximating a range of cut problems such as min cut and sparsest cut. [ABSTRACT FROM AUTHOR]

We consider the consensus interdiction problem (CIP), in which the goal is to maximize the convergence time of consensus averaging dynamics subject to removing a limited number of network edges. We first show that CIP can be cast as an effective resistance interdiction problem (ERIP), in which the goal is to remove a limited number of network edges to maximize the effective resistance between a source node and a sink node. We show that ERIP is strongly NP-hard, even for bipartite graphs of diameter three with fixed source/sink edges, and establish the same hardness result for the CIP. We then show that both ERIP and CIP cannot be approximated up to a (nearly) polynomial factor assuming the exponential time hypothesis. Subsequently, we devise a polynomialtime mn-approximation algorithm for the ERIP that only depends on the number of nodes n and the number of edges m but is independent of the size of edge resistances. Finally, using a quadratic program formulation for the CIP, we devise an iterative approximation algorithm to find a first-order stationary solution for the CIP and evaluate its good performance through numerical experiments. [ABSTRACT FROM AUTHOR]

We focus on convex semi-infinite programs with an infinite number of quadratically parametrized constraints. In our setting, the lower-level problem, i.e., the problem of finding the constraint that is the most violated by a given point, is not necessarily convex. We propose a new convergent approach to solve these semi-infinite programs. Based on the Lagrangian dual of the lower-level problem, we derive a convex and tractable restriction of the considered semi-infinite programming problem. We state sufficient conditions for the optimality of this restriction. If these conditions are not met, the restriction is enlarged through an inner-outer approximation algorithm, and its value converges to the value of the original semi-infinite problem. This new algorithmic approach is compared with the classical cutting plane algorithm. We also propose a new rate of convergence of the cutting plane algorithm, directly related to the iteration index, derived when the objective function is strongly convex, and under a strict feasibility assumption. We successfully test the two methods on two applications: the constrained quadratic regression and a zero-sum game with cubic payoff. Our results are compared to those obtained using the approach proposed in [A. Mitsos, Optimization, 60 (2011), pp. 1291-1308], as well as using the classical relaxation approach based on the KKT conditions of the lower-level problem. [ABSTRACT FROM AUTHOR]

Obtaining strong linear relaxations for capacitated covering problems constitutes a significant technical challenge. For one of the most basic cases, the relaxation based on knapsackcover inequalities has an integrality gap of 2. We generalize the setting considering items that can be taken fractionally to cover a given demand, with a cost given by an arbitrary nondecreasing function (not necessarily convex) of the chosen fraction. We generalize the knapsack-cover inequalities and use them to obtain a polynomial (2 + \varepsilon)-approximation algorithm. Our primal-dual procedure has a natural interpretation as a water-filling algorithm, which overcomes the difficulties implied by having different growth rates in the cost functions: when the cost of an item increases slowly at some superior segment, it carefully increases the priority of all preceding segments. We generalize our algorithm to the Unsplittable Flow-Cover problem on a line, also for fractional items with nonlinear costs. We obtain a 4-approximation in pseudopolynomial time (4 + \varepsilon in polynomial time), matching the approximation ratio of the classical setting. We also present a rounding algorithm with an approximation guarantee of 2. This result is coupled with a polynomial time separation algorithm that allows solving our linear relaxation up to a loss of a (1 + \varepsilon) factor. [ABSTRACT FROM AUTHOR]

A classical branch of graph algorithms is graph transversals, where one seeks a minimum-weight subset of nodes in a node-weighted graph G which intersects all copies of subgraphs F from a fixed family\scrF. Many such graph transversal problems have been shown to admit polynomial-time approximation schemes (PTASs) for planar input graphs G, using a variety of techniques like the shifting technique [B. S. Baker, J. ACM, 41 (1994), pp. 153--180], bidimensionality [F. V. Fomin et al., Bidimensionality and EPTAS, in Proceedings of SODA 2011, ACM, New York, SIAM, Philadelphia, 2011, pp. 748--759], or connectivity domination [V. Cohen-Addad et al., Approximating connectivity domination in weighted bounded-genus graphs, in Proceedings of STOC 2016, ACM, New York, 2016, pp. 584--597]. These techniques do not seem to apply to graph transversals with parity constraints, which have recently received significant attention, but for which no PTASs are known. In the Even Cycle Transversal (ECT) problem, the goal is to find a minimum-weight hitting set for the set of even cycles in an undirected graph. For ECT, Fiorini, Joret, and Pietropaoli [Hitting diamonds and growing cacti, in Proceedings of IPCO 2010, Lecture Notes in Comput. Sci. 6080, Springer, Berlin, 2010, pp. 191--204] showed that the integrality gap of the standard covering LP relaxation is\Theta (log n), and that adding sparsity inequalities reduces the integrality gap to 10. Our main result is a primal-dual algorithm that yields a 47/7\approx 6.71-approximation for ECT on node-weighted planar graphs, and an integrality gap upper bound of the same value for the standard LP relaxation on node-weighted planar graphs. [ABSTRACT FROM AUTHOR]

We consider robust variants of the bin packing problem with uncertain item sizes. Specifically we consider two uncertainty sets previously studied in the literature. The first is budgeted uncertainty (the U\Gamma model), in which at most \Gamma items deviate, each reaching its peak value, while other items assume their nominal values. The second uncertainty set, the U\Omega model, bounds the total amount of deviation in each scenario. We show that a variant of the Next-cover algorithm is a 2 approximation for the U\Omega model, and another variant of this algorithm is a 2\Gamma approximation for the U\Gamma model. Unlike the classical bin packing problem, it is shown that (unless \scrP " \scrN \scrP) no asymptotic approximation scheme exists for the U\Gamma model, for \Gamma " 1. This motivates the question of the existence of a constant approximation factor algorithm for the U\Gamma model. Our main result is to answer this question by proving a (polynomial-time) 4.5 approximation algorithm, based on a dynamic-programming approach. [ABSTRACT FROM AUTHOR]

Recently, Wang and Hu [Theory Probab. Appl., 63 (2019), pp. 479-499] established the Berry-Esseen bounds for ρ-mixing random variables (r.v.'s) with the rate of normal approximation O(n-1/6 log n) by using the martingale method. In this paper, we establish some general results on the rates of normal approximation, which include the corresponding ones of Wang and Hu. The rate can be as high as O(n-1/5) or O(n-1/4 log1/2 n) under some suitable conditions. As applications, we obtain the Berry-Esseen bounds of sample quantiles based on ρ-mixing random samples. Finally, we also present some numerical simulations to demonstrate finite sample performances of the theoretical result. [ABSTRACT FROM AUTHOR]

We revisit Min-Mean-Cycle, the classical problem of finding a cycle in a weighted directed graph with minimum mean weight. Despite an extensive algorithmic literature, previous work failed to achieve a near-linear runtime in the number of edges m. We propose an algorithm with near-linear runtime Õ(m(Wmax/ε)²) for computing an e additive approximation on graphs with polylogarithmic diameter and weights of magnitude at most Wmax. In particular, this is the first algorithm whose runtime scales in the number of vertices n as Õ(n²) for the complete graph. Moreover--unconditionally on the diameter--the algorithm uses only O(n) memory beyond reading the input, making it "memory-optimal". Our approach is based on solving a linear programming (LP) relaxation using entropic regularization, which reduces the LP to a Matrix Balancing problem--à la the popular reduction of Optimal Transport to Matrix Scaling. We then round the fractional LP solution using a variant of the classical Cycle-Canceling algorithm that is sped up to near-linear runtime at the expense of being approximate, and implemented in a memory-optimal manner. The algorithm is simple to implement and is competitive with the state-of-the-art methods in practice. [ABSTRACT FROM AUTHOR]

The stochastic auxiliary problem principle (APP) algorithm is a general stochastic approximation (SA) scheme that turns the resolution of an original convex optimization problem into the iterative resolution of a sequence of auxiliary problems. This framework has been introduced to design decomposition-coordination schemes but also encompasses many well-known SA algorithms such as stochastic gradient descent or stochastic mirror descent. We study the stochastic APP in the case where the iterates lie in a Banach space and we consider an additive error on the computation of the subgradient of the objective. In order to derive convergence results or efficiency estimates for an SA scheme, the iterates must be random variables. This is why we prove the measurability of the iterates of the stochastic APP algorithm. Then, we extend convergence results from the Hilbert space case to the reflexive separable Banach space case. Finally, we derive efficiency estimates for the function values taken at the averaged sequence of iterates or at the last iterate, the latter being obtained by adapting the concept of modified Fejér monotonicity to our framework. [ABSTRACT FROM AUTHOR]

Longest common subsequence (LCS) is one of the most fundamental problems in combinatorial optimization. Apart from theoretical importance, LCS has enormous applications in bioinformatics, revision control systems, and data comparison programs. Although a simple dynamic program computes LCS in quadratic time, it has been recently proven that the problem admits a conditional lower bound and may not be solved in truly subquadratic time [2, 18]. In addition to this, LCS is notoriously hard with respect to approximation algorithms. Apart from a trivial sampling technique that obtains an nx approximation solution in time O(n2-2x) nothing else is known for LCS. This is in sharp contrast to its dual problem edit distance, for which several linear time solutions were obtained in the past two decades [5, 6, 10, 11, 19]. In this work, we present the first nontrivial algorithm for approximating LCS in linear time. Our main result is a linear time algorithm for the LCS which has an approximation factor of O(n0.4991319) in expectation. This beats the √n barrier for approximating LCS in linear time. [ABSTRACT FROM AUTHOR]

We consider two generalizations of the classical weighted paging problem that incorporate the notion of delayed service of page requests. The first is the (weighted) paging with time windows (PageTW) problem, which is like the classical weighted paging problem except that each page request only needs to be served before a given deadline. This problem arises in many practical applications of online caching, such as the "deadline"" I/O scheduler in the Linux kernel and video-on-demand streaming. The second, and more general, problem is the (weighted) paging with delay (PageD) problem, where the delay in serving a page request results in a penalty being added to the objective. This problem generalizes the caching problem to allow delayed service, a line of work that has recently gained traction in online algorithms (e.g., [Y. Emek, S. Kutten, and R. Wattenhofer, Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016, pp. 333--344; Y. Azar et al., Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017, pp. 551--563; Y. Azar and N. Touitou, Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019, pp. 60--71]). We give O(log k log n)-competitive algorithms for both the PageTW and PageD problems on n pages with a cache of size k. This significantly improves on the previous best bounds of O(k) for both problems [Y. Azar et al., Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017, pp. 551--563]. We also consider the offline PageTW and PageD problems, for which we give O(1)-approximation algorithms and prove APX-hardness. These are the first results for the offline problems; even NP-hardness was not known before our work. At the heart of our algorithms is a novel "hitting-set"" LP relaxation of the PageTW problem that overcomes the\Omega (k) integrality gap of the natural LP for the problem. To the best of our knowledge, this is the first example of an LP-based algorithm for an online problem with delays/deadlines. [ABSTRACT FROM AUTHOR]

We revisit the constant-factor approximation algorithm for the asymmetric traveling salesman problem by Svensson, Tarnawski, and V\'egh [J. ACM, 67 (2020), 37]. We improve on each part of this algorithm. We avoid the reduction to irreducible instances and thus obtain a simpler and much better reduction to vertebrate pairs. We also show that a slight variant of their algorithm for vertebrate pairs has a much smaller approximation ratio. Overall we improve the approximation ratio from 506 to 22 + ε for any ε > 0. This also improves the upper bound on the integrality ratio from 319 to 22. [ABSTRACT FROM AUTHOR]

Horn functions form an important subclass of Boolean functions and appear in many different areas of computer science and mathematics as a general tool to describe implications and dependencies. Finding minimum sized representations for such functions with respect to most commonly used measures is a computationally hard problem admitting a 2log1-o(1) n inapproximability bound. In this paper we consider the natural class of key Horn functions representing keys of relational databases. For this class, the minimization problems for most measures remain NP-hard. In this paper we provide logarithmic factor approximation algorithms for key Horn functions with respect to all such measures. [ABSTRACT FROM AUTHOR]

Maximizing a monotone submodular function under various constraints is a classical and intensively studied problem. However, in the single-pass streaming model, where the elements arrive one by one and an algorithm can store only a small fraction of input elements, there is large gap in our knowledge, even though several approximation algorithms have been proposed in the literature. In this work, we present the first lower bound on the approximation ratios for cardinality and matroid constraints that beat 1- 1 e in the single-pass streaming model. Let n be the number of elements in the stream. Then, we prove that any (randomized) streaming algorithm for a cardinality constraint with approximation ratio 2- v 2+e requires O(n K2) space for any e > 0, where K is the size limit of the output set. We also prove that any (randomized) streaming algorithm for a (partition) matroid constraint with approximation ratio K 2K-1 + e requires O(n K2) space for any e > 0, where K is the rank of the given matroid. In addition, we give streaming algorithms that assume access to the objective function via a weak oracle that can only be used to evaluate function values on feasible sets. Specifically, we show weak-oracle streaming algorithms for cardinality and matroid constraints with approximation ratios K 2K-1 and 1 2, respectively, whose space complexity is exponential in K but is independent of n. The former one exactly matches the known inapproximability result for a cardinality constraint in the weak oracle model. The latter one almost matches our lower bound of K 2K-1 for a matroid constraint, which almost settles the approximation ratio for a matroid constraint that can be obtained by a streaming algorithm whose space complexity is independent of n. [ABSTRACT FROM AUTHOR]

The minimum majority problem is as follows: given a matrix $A \in \{-1, 1\}^{m \times n}$, minimize $\sum_{i=1}^n x_i$ subject to $A {x} \geq {1}$ and ${x} \in ({\mathbb Z}^+)^n$. An approximation algorithm that finds a solution with value $O({opt}^2 \log m)$ in ${poly}(m,n,{opt})$ time is known, which can be obtained by rounding a linear programming relaxation. We establish integrality gaps that limit the prospects for improving upon this guarantee through improved rounding and/or the application of Lovász--Schrijver (LS) or Sherali--Adams (SA) tightening of the relaxation. These gaps show that applying LS and SA relaxations cannot improve upon the $O({opt}^2 \log m)$ guarantee by more than a constant factor in polynomial time. [ABSTRACT FROM AUTHOR]

We present an extension of the AAA (adaptive Antoulas--Anderson) algorithm for periodic functions, called "AAAtrig."" The algorithm uses the key steps of AAA approximation by (i) representing the approximant in (trigonometric) barycentric form and (ii) selecting the support points greedily. Accordingly, AAAtrig inherits all the favorable characteristics of AAA and is thus extremely flexible and robust, being able to consider quite general sets of sample points in the complex plane. We consider a range of applications with particular emphasis on solving Laplace's equation in periodic domains and compressing periodic conformal maps. These results reproduce the tapered exponential clustering effect observed in other recent studies. The algorithm is implemented in Chebfun. [ABSTRACT FROM AUTHOR]

A selection of algorithms for the rational approximation of matrix-valued functions are discussed, including variants of the interpolatory adaptive Antoulas--Anderson (AAA) method, the rational Krylov fitting (RKFIT) method based on approximate least squares fitting, vector fitting, and a method based on low-rank approximation of a block Loewner matrix. A new method, called the block-AAA algorithm, based on a generalized barycentric formula with matrix-valued weights, is proposed. All algorithms are compared in terms of obtained approximation accuracy and runtime on a set of problems from model order reduction and nonlinear eigenvalue problems, including examples with noisy data. It is found that interpolation-based methods are typically cheaper to run, but they may suffer in the presence of noise for which approximation-based methods perform better. [ABSTRACT FROM AUTHOR]

We give a polynomial time approximation scheme for the weighted traveling re- pairman problem (TRP) in the Euclidean plane, on trees, and on planar graphs. This improves upon the quasi-polynomial time approximation schemes for the unweighted TRP in the Euclidean plane and trees and on the 3.59-approximation for planar graphs. The algorithms are based on a new decomposition technique that reduces the approximation of weighted TRP to instances for which we may restrict ourselves to solutions that are the concatenation of only a constant number of traveling salesman problem paths. A similar reduction applies to many other problems with an average completion time objective. To illustrate the strength of this approach, we apply the same technique to the well-studied scheduling problem of minimizing total weighted completion time under precedence constraints, 1/prec/∑wjCj, and present a polynomial time approximation scheme for the case of interval order precedence constraints. This improves on the known 3/2-approximation for this problem. [ABSTRACT FROM AUTHOR]

Fundamental in matrix algebra and its applications, a generalized inverse of a real matrix A is a matrix H that satisfies the Moore--Penrose (M--P) property AH A = A. If H also satisfies the additional useful M--P property, H AH = H, it is called a reflexive generalized inverse. Reflexivity is equivalent to minimum rank, so we are particularly interested in reflexive generalized inverses. We consider aspects of symmetry related to the calculation of a sparse reflexive generalized inverse of A. As is common, and following Fampa and Lee [Oper. Res. Lett., 46 (2018), pp. 605-610] for calculating sparse generalized inverses, we use (vector) 1-norm minimization for inducing sparsity and for keeping the magnitude of entries under control. When A is symmetric, we may naturally desire a symmetric H, while generally such a restriction on H may not lead to a 1-norm minimizing reflexive generalized inverse. We investigate a block construction method to produce a symmetric reflexive generalized inverse that is structured and has guaranteed sparsity. We provide a theoretically efficient and practical local-search algorithm to block construct an approximate 1-norm minimizing symmetric reflexive generalized inverse. Another aspect of symmetry that we consider relates to another M--P property: H is ah-symmetric if AH is symmetric. The ah-symmetry property is the key one for solving least-squares problems using H. Here we do not assume that A is symmetric, and we do not impose symmetry on H. We investigate a column block construction method to produce an ah-symmetric reflexive generalized inverse that is structured and has guaranteed sparsity. We provide a theoretically efficient and practical local-search algorithm to column block construct an approximate 1-norm minimizing ah-symmetric reflexive generalized inverse. [ABSTRACT FROM AUTHOR]

Among the most important graph parameters is the diameter, the largest distance between any two vertices. There are no known very efficient algorithms for computing the diameter exactly. Thus, much research has been devoted to how fast this parameter can be approximated. Chechik et al. [Proceedings of SODA 2014, Portland, OR, 2014, pp. 1041-1052] showed that the diameter can be approximated within a multiplicative factor of 3/2 in ~(m3/2) time. Furthermore, Roditty and Vassilevska W. [Proceedings of STOC '13, New York, ACM, 2013, pp. 515-524] showed that unless the strong exponential time hypothesis (SETH) fails, no O(n2\varepsilon) time algorithm can achieve an approximation factor better than 3/2 in sparse graphs. Thus the above algorithm is essentially optimal for sparse graphs for approximation factors less than 3/2. It was, however, completely plausible that a 3/2-approximation is possible in linear time. In this work we conditionally rule out such a possibility by showing that unless SETH fails no O(m3/2\varepsilon) time algorithm can achieve an approximation factor better than 5/3. Another fundamental set of graph parameters is the eccentricities. The eccentricity of a vertex v is the distance between v and the farthest vertex from v. Chechik et al. [Proceedings of SODA 2014, Portland, OR, 2014, pp. 1041-1052] showed that the eccentricities of all vertices can be approximated within a factor of 5/3 in ~ (m3/2) time and Abboud, Vassilevska W., and Wang [Proceedings of SODA 2016, Arlington, VA, 2016, pp. 377-391] showed that no O(n2\varepsilon) algorithm can achieve better than 5/3 approximation in sparse graphs. We show that the runtime of the 5/3 approximation algorithm is also optimal by proving that under SETH, there is no O(m3/2\varepsilon) algorithm that achieves a better than 9/5 approximation. We also show that no near-linear time algorithm can achieve a better than 2 approximation for the eccentricities. This is the first lower bound in fine-grained complexity that addresses near-linear time computation. We show that our lower bound for near-linear time algorithms is essentially tight by giving an algorithm that approximates eccentricities within a 2 + \delta factor in ~(m/\delta) time for any 0 < \delta < 1. This beats all eccentricity algorithms in Cairo, Grossi, and Rizzi [Proceedings of SODA 2016, Arlington, VA, 2016, pp. 363-376] and is the first constant factor approximation for eccentricities in directed graphs. To establish the above lower bounds we study the S-T diameter problem: Given a graph and two subsets S and T of vertices, output the largest distance between a vertex in S and a vertex in T. We give new algorithms and show tight lower bounds that serve as a starting point for all other hardness results. Our lower bounds apply only to sparse graphs. We show that for dense graphs, there are near-linear time algorithms for S-T diameter, diameter, and eccentricities, with almost the same approximation guarantees as their ~(m3/2) counterparts, improving upon the best known algorithms for dense graphs. [ABSTRACT FROM AUTHOR]

The characterization of all the constraint satisfaction problems solvable by local consistency checking (also known as CSPs of bounded width) was proposed by Feder and Vardi [SIAM J. Comput., 28 (1998), pp. 57104]. It was confirmed by two independent proofs by Bulatov [Bounded Relational Width, manuscript, 2009] and Barto and Kozik [L. Barto and M. Kozik, 50th Annual IEEE Symposium on Foundations of Computer Science, 2009, pp. 595 603], [L. Barto and M. Kozik, J. ACM, 61 (2014), 3]. Later Barto [J. Logic Comput., 26 (2014), pp. 923 943] proved a collapse of the hierarchy of local consistency notions by showing that (2; 3) minimality solves all the CSPs of bounded width. In this paper we present a new consistency notion, jpq consistency, which also solves all the CSPs of bounded width. Our notion is strictly weaker than (2; 3) consistency, (2; 3) minimality, path consistency, and singleton arc consistency (SAC). This last fact allows us to answer the question of Chen, Dalmau, and Gruien [J. Logic Comput., 23 (2013), pp. 87 108] by confirming that SAC solves all the CSPs of bounded width. Moreover, as known algorithms work faster for SAC, the result implies that CSPs of bounded width can be, in practice, solved more efficiently. The definition of jpq consistency is closely related to a consistency condition obtained from the rounding of an SDP relaxation of a CSP instance. In fact, the main result of this paper is used by Dalmau et al. [Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, ACM, New York, 2017, pp. 340{357] to show that CSPs with near unanimity polymorphisms admit robust approximation algorithms with polynomial loss. Finally, an algebraic characterization of some term conditions satisfied in algebras associated with templates of bounded width, first proved by Brady, is a direct consequence of our result. [ABSTRACT FROM AUTHOR]

Suppose we are given a bipartite graph that admits a perfect matching and an adversary may delete any edge from the graph with the intention of destroying all perfect matchings. We consider the task of adding a minimum-cost edge-set to the graph such that the adversary never wins. We show that this problem is equivalent to covering a digraph with nontrivial strongly connected components at minimal cost. We provide efficient exact and approximation algorithms for this task. In particular, for the unit-cost problem, we give a log2 n-factor approximation algorithm and a polynomial-time algorithm for chordal-bipartite graphs. Furthermore, we give a fixed parameter algorithm for the problem parameterized by the treewidth of the input graph. For general nonnegative weights we give tight upper and lower approximation bounds relative to the directed Steiner forest problem. Additionally, we prove a dichotomy theorem characterizing minor-closed graph classes which allow for a polynomial-time algorithm. To obtain our results, we exploit a close relation to the classical strong connectivity augmentation problem as well as directed Steiner problems. [ABSTRACT FROM AUTHOR]