Search

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]

We address the fundamental network design problem of constructing approximate minimum spanners. Our contributions are for the distributed setting, providing both algorithmic and hardness results. Our main hardness result shows that an ∝-approximation for the minimum directed k-spanner problem for k ≥ 5 requires Ω(n/√∝ logn) rounds using deterministic algorithms or Ω(√n/√∝ logn) rounds using randomized ones, in the Congest model of distributed computing. Combined with the constant-round O(nε)-approximation algorithm in the Local model of [L. Barenboim, M. Elkin, and C. Gavoille, Theoret. Comput. Sci., 751 (2016), pp. 2-23], as well as a polylog-round (1 + ε)-approximation algorithm in the Local model that we show here, our lower bounds for the Congest model imply a strict separation between the Local and Congest models. Notably, to the best of our knowledge, this is the first separation between these models for a local approximation problem. Similarly, a separation between the directed and undirected cases is implied. We also prove hardness results for weighted k-spanners and for unweighted undirected k-spanners for k ≥ 4 in the Congest model. In addition, we show lower bounds for the minimum weighted 2-spanner problem in the Congest and Local models. On the algorithmic side, apart from the aforementioned (1+ε)-approximation algorithm for minimum k-spanners, our main contribution is a new distributed construction of minimum 2-spanners that uses only polynomial local computations. Our algorithm has a guaranteed approximation ratio of O(log(m/n)) for a graph with n vertices and m edges, which matches the best known ratio for polynomial-time sequential algorithms [G. Kortsarz and D. Peleg, J. Algorithms, 17 (1994), pp. 222-236], and is tight if we restrict ourselves to polynomial local computations. An algorithm with this approximation factor was not previously known for the distributed setting. The number of rounds required for our algorithm is O(log n log Δ) with high probability, where Δ is the maximum degree in the graph. Our approach allows us to extend our algorithm to work also for the directed, weighted, and client-server variants of the problem. It also provides a Congest algorithm for the minimum dominating set problem, with a guaranteed O(log Δ) approximation ratio. [ABSTRACT FROM AUTHOR]

We resolve the space complexity of single-pass streaming algorithms for approximating the classic set cover problem. For finding an α-approximate set cover (for any α = o(√n/log n)) using a single-pass streaming algorithm, we show that Θ(mn/α) space is both sufficient and necessary (up to an O(log n) factor); here m denotes the number of sets and n denotes the size of the universe. This provides a strong negative answer to the open question posed by Har-Peled et al. [Towards tight bounds for the streaming set cover problem, in Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS '16), pp. 371-383] regarding the possibility of having a single-pass algorithm with a small approximation factor that uses sublinear space. We further study the problem of estimating the size of a minimum set cover (as opposed to finding the actual sets) and establish that an additional factor of α savings in the space is achievable in this case and is the best possible. In other words, we show that Θ(mn/α²) space is both sufficient and necessary (up to logarithmic factors) for estimating the size of a minimum set cover to within a factor of α. Our algorithm, in fact, works for the more general problem of estimating the optimal value of a covering integer program. On the other hand, our lower bound holds even for set cover instances, where the sets are presented in a random order. [ABSTRACT FROM AUTHOR]

In a classical problem in scheduling, one has n unit size jobs with a precedence order and the goal is to find a schedule of those jobs on m identical machines as to minimize the makespan. It is one of the remaining four open problems from the book of Garey & Johnson whether or not this problem is NP-hard for m=3. We prove that for any fixed ε and m, an LP-hierarchy lift of the time-index LP with a slightly super poly-logarithmic number of r = (log(n))Θ(loglogn) rounds provides a (1 + ε)-approximation. For example Sherali-Adams suffices as hierarchy. This implies an algorithm that yields a (1+ε)-approximation in time nO(r). The previously best approximation algorithms guarantee a 2 - 7/3m+1-approximation in polynomial time for m ≥ 4 and 4/3 for m=3. Our algorithm is based on a recursive scheduling approach where in each step we reduce the correlation in form of long chains. Our method adds to the rather short list of examples where hierarchies are actually useful to obtain better approximation algorithms. [ABSTRACT FROM AUTHOR]

We consider the problem of scheduling jobs on unrelated machines so as to minimize the sum of weighted completion times. Our main result is a (3/2 c)-approximation algorithm for some fixed c > 0, improving upon the long-standing bound of 3/2. To do this, we first introduce a new lift-and-project-based SDP relaxation for the problem. This is necessary, as the previous convex programming relaxations have an integrality gap of 3/2. Second, we give a new general bipartiterounding procedure that produces an assignment with certain strong negative correlation properties. [ABSTRACT FROM AUTHOR]

Persuasion, defined as the act of exploiting an informational advantage in order to inuence the decisions of others, is ubiquitous. Indeed, persuasive communication has been estimated to account for almost a third of all economic activity in the U.S. This paper examines persuasion through a computational lens, focusing on what is perhaps the most basic and fundamental model in this space: the celebrated Bayesian persuasion model of Kamenica and Gentzkow [Am. Econ. Rev., 101 (2011), pp. 2590-2615]. Here there are two players, a sender and a receiver. The receiver must take one of a number of actions with an a priori unknown payoff, and the sender has access to additional information regarding the payoffs of the various actions for both players. The sender can commit to revealing a noisy signal regarding the realization of the payoffs of various actions, and would like to do so to maximize her own payoff in expectation assuming that the receiver rationally acts to maximize his own payoff. When the payoffs of various actions follow a joint distribution (the common prior), the sender's problem is nontrivial, and its computational complexity depends on the representation of this prior. We examine the sender's optimization task in three of the most natural input models for this problem, and essentially pin down its computational complexity in each. When the payoff distributions of the different actions are independently and identically distributed (i.i.d.) and given explicitly, we exhibit a polynomial-time (exact) algorithmic solution, and a "simple" (1-1=e)-approximation algorithm. Our optimal scheme for the i.i.d. setting involves an analogy to auction theory, and makes use of Border's characterization of the space of reduced-forms for single-item auctions. When action payoffs are independent but nonidentical with marginal distributions given explicitly, we show that it is #P-hard to compute the optimal expected sender utility. In doing so, we rule out a generalized Border's theorem, in the sense of Gopalan, Nisan, and Roughgarden [Public projects, boolean functions, and the borders of Border's theorem, in Proceedings of the Sixteenth ACM Conference on Economics and Computation, EC '15, ACM, New York, 2015, p. 395], for this setting. Finally, we consider a general (possibly correlated) joint distribution of action payoffs presented by a black box sampling oracle, and exhibit a fully polynomial-time approximation scheme (FPTAS) with a bicriteria guarantee. Our FPTAS is based on Monte Carlo sampling, and its analysis relies on the principle of deferred decisions. Moreover, we show that this result is the best possible in the black-box model for information-theoretic reasons. [ABSTRACT FROM AUTHOR]

We study a central problem in algorithmic mechanism design: constructing truthful mechanisms for welfare maximization in combinatorial auctions with submodular bidders. Dobzinski, Nisan, and Schapira provided the first mechanism that guarantees a nontrivial approximation ratio of O(log²m) [STOC'06, ACM, New York, 2006, pp. 644-652], where m is the number of items. This approximation ratio was subsequently improved to O(logmlog logm) [S. Dobzinski, APPROX'07, Springer, Berlin, 2007, pp. 89-103] and then to O(logm) [P. Krysta and B. Vöcking, ICALP'12, Springer, Heidelberg, 2012, pp. 636-647]. In this paper we develop the first mechanism that breaks the logarithmic barrier. Specifically, the mechanism provides an approximation ratio of O(√logm). Similarly to previous constructions, our mechanism uses polynomially many value and demand queries and, in fact, provides the same approximation ratio for the larger class of XOS (also known as fractionally subadditive) valuations. We also develop a computationally efficient implementation of the mechanism for combinatorial auctions with budget additive bidders. Although, in general, computing a demand query is NP-hard for budget additive valuations, we observe that the specific form of demand queries that our mechanism uses can be efficiently computed when bidders are budget additive. [ABSTRACT FROM AUTHOR]

We provide a comprehensive study of a natural graph optimization problem that arises from transition costs between incident edges. In the problem Minimum Scan Cover with Angular Costs (MSC), we are given a graph G that is embedded in Euclidean space. The edges of G need to be scanned, i.e., probed from both of their vertices. In order to scan their edge, two vertices need to face each other; changing the heading of a vertex takes some time proportional to the corresponding turn angle. Our goal is to minimize the time until all scans are completed, i.e., to compute a schedule of minimum makespan. A real-world motivation arises in the context of satellite communication and astrophysics. We show that MSC is closely related to both graph coloring and the minimum (directed and undirected) cut cover problem; in particular, we show that the minimum scan time for instances in 1D and 2D lies in Theta (log chi (G)), while for 3D the minimum scan time is not upper bounded by chi (G). We use this relationship to prove that the existence of a constant-factor approximation implies P = NP, even for one-dimensional instances. In 2D, we show that it is NP-hard to approximate a minimum scan cover within less than a factor of 3/2, even for bipartite graphs; conversely, we present a 9/2-approximation algorithm for this scenario. Generally, we give an O(c)-approximation for k-colored graphs with k leq chi (G)c. For general metric cost functions, we provide approximation algorithms whose performance guarantees depend on the arboricity of the graph. [ABSTRACT FROM AUTHOR]

Given an n-vertex m-edge graph G with nonnegative edge-weights, a shortest cycle is one minimizing the sum of the weights on its edges. The girth of G is the weight of a shortest cycle. We obtain several new approximation algorithms for computing the girth of weighted graphs: For any graph G with polynomially bounded integer weights, we present a deterministic algorithm that computes, in scrO (n5/3 + m)-time, a cycle of weight at most twice the girth of G. This matches the approximation factor of the best known subquadratic-time approximation algorithm for the girth of unweighted graphs. Then, we turn our algorithm into a deterministic (2 + varepsilon)-approximation for graphs with arbitrary nonnegative edge-weights, at the price of a slightly worse running time in scrO (n5/3polylog(1varepsilon)+m). For that, we introduce a generic method in order to obtain a polynomialfactor approximation of the girth in subquadratic time, that may be of independent interest. Finally, if we assume that the adjacency lists are sorted then we can get rid off the dependency in the number m of edges. Namely, we can transform our algorithms into an crO (n5/3)-time randomized 4-approximation for graphs with nonnegative edge-weights. This can be derandomized, thereby leading to an crO (n5/3)-time deterministic 4-approximation for graphs with polynomially bounded integer weights, and an scrO (n53polylog(1varepsilon))-time deterministic (4+varepsilon)-approximation for graphs with nonnegative edge-weights. To the best of our knowledge, these are the first known subquadratic-time approximation algorithms for computing the girth of weighted graphs. [ABSTRACT FROM AUTHOR]

Treedepth, a more restrictive graph width parameter than treewidth and pathwidth, plays a major role in the theory of sparse graph classes. We show that there exists a constant C such that for all positive integers a, b and a graph G, if the treedepth of G is at least Cab, then the treewidth of G is at least a or G contains a subcubic (i.e., of maximum degree at most 3) tree of treedepth at least b as a subgraph. As a direct corollary, we obtain that every graph of treedepth Omega (k3) either is of treewidth at least k, contains a subdivision of full binary tree of depth k, or contains a path of length 2k. This improves the bound of Omega (k5 log2 k) of Kawarabayashi and Rossman [Proceedings of the 2018 Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 234--246]. We also show an application of our techniques for approximation algorithms of treedepth: given a graph G of treedepth k and treewidth t, one can in polynomial time compute a treedepth decomposition of G of width scrO (kt log3/2 t). This improves upon a bound of scrO (kt2 log t) stemming from a tradeoff between known results. The main technical ingredient in our result is a proof that every tree of treedepth d contains a subcubic subtree of treedepth at least d cdot log3((1 + surd 5)/2). [ABSTRACT FROM AUTHOR]

We devise a constant-factor approximation algorithm for the maximization version of the edge-disjoint paths problem if the supply graph together with the demand edges forms a planar graph. By planar duality, this is equivalent to packing cuts in a planar graph such that each cut contains exactly one demand edge. We also show that the natural linear programming relaxations have constant integrality gap, yielding an approximate max-multiflow min-multicut theorem. [ABSTRACT FROM AUTHOR]

We propose a novel algorithm for the approximation of surface quasi-geostrophic (SQG) flows modeled by a nonlinear partial differential equation coupling transport and fractional diffusion phenomena. The time discretization consists of an explicit strong-stability-preserving three-stage Runge--Kutta method while a flux-corrected-transport (FCT) method coupled with Dunford--Taylor representations of fractional operators is advocated for the space discretization. Standard continuous piecewise linear finite elements are employed, and the algorithm does not have restrictions on the mesh structure or on the computational domain. In the inviscid case, we show that the resulting scheme satisfies a discrete maximum principle property under a standard CFL condition and observe, in practice, its second order accuracy in space. The algorithm successfully approximates several benchmarks with sharp transitions and fine structures typical of SQG flows. In addition, theoretical Kolmogorov energy decay rates are observed on a freely decaying atmospheric turbulence simulation. [ABSTRACT FROM AUTHOR]

An overarching issue in resource management of wireless networks is assessing their capacity: How much communication can be achieved in a network, utilizing all the tools available: power control, scheduling, routing, channel assignment, and rate adjustment? We propose the first framework for approximation algorithms in the physical model of wireless interference that addresses these questions in full in interference-limited networks. The approximations obtained are at most doubly logarithmic in the link length and rate diversity. Where previous bounds are known, this gives an exponential improvement or better. The key insight is the discovery that a properly chosen power assignment infers a form of locality, or tolerance to the interference of both shorter and longer communication links. This allows us to simplify the complex interference relationship of the physical model into a new form of conflict graphs, at a small cost. We also show that the approximation obtained is provably the best possible for any conflict graph formulation. [ABSTRACT FROM AUTHOR]

For an undirected edge-weighted graph G and a set R of pairs of vertices called pairs of terminals, a multicut is a set of edges such that removing these edges from G disconnects each pair in R. We provide an algorithm computing a (1 + ε)-approximation of the minimum multicut of a graph G in time (g + t)(O(g+t)3) · (1/ε)ο(g=+t) ·n log n, where g is the genus of G and t is the number of terminals. This is tight in several aspects, as the minimum multicut problem is both APX-hard and W[1]-hard (parameterized by the number of terminals), even on planar graphs (equivalently, when g = 0). Our result, in the field of fixed-parameter approximation algorithms, mostly relies on concepts borrowed from computational topology of graphs on surfaces. In particular, we use and extend various recent techniques concerning homotopy, homology, and covering spaces. Interestingly, such topological techniques seem necessary even for the planar case. We also exploit classical ideas stemming from approximation schemes for planar graphs and low-dimensional geometric inputs. A key insight toward our result is a novel characterization of a minimum multicut as the union of some Steiner trees in the universal cover of the surface in which G is embedded. [ABSTRACT FROM AUTHOR]

In this paper new general modewise Johnson--Lindenstrauss (JL) subspace embeddings are proposed that can be both generated much faster and stored more easily than traditional JL embeddings when working with extremely large vectors and/or tensors. Corresponding embedding results are then proven for two different types of low-dimensional (tensor) subspaces. The first of these new subspace embedding results produces improved space complexity bounds for embeddings of rank-r tensors whose CP decompositions are contained in the span of a fixed (but unknown) set of r rank-1 basis tensors. In the traditional vector setting this first result yields new and very general near-optimal oblivious subspace embedding constructions that require fewer random bits to generate than standard JL embeddings when embedding subspaces of

We introduce a fast algorithm for entrywise evaluation of the Gauss--Newton Hessian (GNH) matrix for the fully connected feed-forward neural network. The algorithm has a precomputation step and a sampling step. While it generally requires O(Nri) work to compute an entry (and the entire column) in the GNH matrix for a neural network with N parameters and n data points, our fast sampling algorithm reduces the cost to O(n + d/e²) work, where d is the output dimension of the network and e is a prescribed accuracy (independent of N). One application of our algorithm is constructing the hierarchical-matrix (H-matrix) approximation of the GNH matrix for solving linear systems and eigenvalue problems. It generally requires O(N²) memory and O(N³) work to store and factorize the GNH matrix, respectively. The 'H-matrix approximation requires only O(Nro) memory footprint and O(Nr°) work to be factorized, where ro O N is the maximum rank of off-diagonal blocks in the GNH matrix. We demonstrate the performance of our fast algorithm and the H-matrix approximation on classification and autoencoder neural networks. [ABSTRACT FROM AUTHOR]

We study the Steiner Tree problem, in which a set of terminal vertices needs to be connected in the cheapest possible way in an edge-weighted graph. This problem has been extensively studied from the viewpoint of approximation and also parameterization. In particular, on one hand Steiner Tree is known to be sansA sansP sansX -hard, and sansW [sanstwo ]-hard on the other, if parameterized by the number of nonterminals (Steiner vertices) in the optimum solution. In contrast to this, we give an efficient parameterized approximation scheme (sansE sansP sansA sansS), which circumvents both hardness results. Moreover, our methods imply the existence of a polynomial size approximate kernelization scheme (sansP sansS sansA sansK sansS) for the considered parameter. We further study the parameterized approximability of other variants of Steiner Tree, such as Directed Steiner Tree and Steiner Forest. For none of these is an sansE sansP sansA sansS likely to exist for the studied parameter. For Steiner Forest an easy observation shows that the problem is sansA sansP sansX -hard, even if the input graph contains no Steiner vertices. For Directed Steiner Tree we prove that approximating within any function of the studied parameter is sansW [sansone ]-hard. Nevertheless, we show that an sansE sansP sansA sansS exists for Unweighted Directed Steiner Tree, but a sansP sansS sansA sansK sansS does not. We also prove that there is an sansE sansP sansA sansS and a sansP sansS sansA sansK sansS for Steiner Forest if in addition to the number of Steiner vertices, the number of connected components of an optimal solution is considered to be a parameter. [ABSTRACT FROM AUTHOR]

Suppose scrF is a finite family of graphs. We consider the following meta-problem, called scrF -Immersion Deletion: given a graph G and integer k, decide whether the deletion of at most k edges of G can result in a graph that does not contain any graph from scrF as an immersion. This problem is a close relative of the scrF -Minor Deletion problem studied by Fomin et al. [Proceedings of FOCS, IEEE, 2012, pp. 470--479], where one deletes vertices in order to remove all minor models of graphs from scrF. We prove that whenever all graphs from scrF are connected and at least one graph of scrF is planar and subcubic, then the scrF -Immersion Deletion problem admits a constant-factor approximation algorithm running in time scrO (m3 cdot n3 cdot logm), a linear kernel that can be computed in time scrO (m4 cdot n3 cdot logm), and a scrO (2scrO (k) +m4 cdot n3 cdot logm)-time fixed-parameter algorithm, where n,m count the vertices and edges of the input graph. These results mirror the findings of Fomin et al., who obtained a similar set of algorithmic results for scrF -Minor Deletion, under the assumption that at least one graph from scrF is planar. An important difference is that we are able to obtain a linear kernel for scrF -Immersion Deletion, while the exponent of the kernel of Fomin et al. for scrF -Minor Deletion depends heavily on the family scrF. In fact, this dependence is unavoidable under plausible complexity assumptions, as proven by Giannopoulou et al. [ACM Trans. Algorithms, 13 (2017), p. 35]. This reveals that the kernelization complexity of scrF -Immersion Deletion is quite different from that of scrF -Minor Deletion. [ABSTRACT FROM AUTHOR]

Submodularity is one of the most important properties in combinatorial optimization, and k-submodularity is a generalization of submodularity. Maximization of a k-submodular function requires an exponential number of value oracle queries, and approximation algorithms have been studied. For unconstrained k-submodular maximization, Iwata, Tanigawa, and Yoshida, [Improved approximation algorithms for k-submodular function maximization, in Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 2016, pp. 404-413] gave a randomized k/(2k 1)-approximation algorithm for monotone functions and a randomized 1/2-approximation algorithm for nonmonotone functions. In this paper, we present improved randomized algorithms for nonmonotone functions. Our algorithm gives a k2+1 2k2+1 -approximation for k geq 3. We also give a randomized surd 17 3 2 -approximation algorithm for k = 3. We use the same framework used in Iwata, Tanigawa, and Yoshida, [Improved approximation algorithms for k-submodular function maximization, in Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 2016, pp. 404--413] and Ward and v Zivn'y [ACM Trans. Algorithms, 12 (2016), pp. 46:1--47:26] with different probabilities. [ABSTRACT FROM AUTHOR]

An artificial boundary method is developed for solving the one-dimensional advection diffusion equation in the real line. In order to construct a fully discrete fast numerical algorithm with rigorous error analysis, we start with the two-step backward difference formula for time discretization of the advection diffusion equation in the whole real line. Then, we use the discrete analogue of the Laplace transform to derive a second-order time-stepping scheme in a bounded domain equipped with a discrete artificial boundary condition (ABC). The Galerkin finite element method is used for spatial discretization. To expedite the evaluation of time convolution involved in the discrete ABC, we propose a fast algorithm based on the best rational approximation of square root function in subdomains of the complex plane. An estimate for this best rational approximation enables us to prove optimal-order convergence of the fully discrete numerical scheme (integrating the fast approximation algorithm). Several numerical examples are provided to illustrate the convergence of numerical solutions and the effectiveness of the proposed fast approximation algorithm. [ABSTRACT FROM AUTHOR]

Several fundamental problems that arise in optimization and computer science can be cast as follows: Given vectors v1, . . ., vm È Rd and a constraint family B \subseteq 2[m], find a set S ÈB that maximizes the squared volume of the simplex spanned by the vectors in S. A motivating example is the ubiquitous data-summarization problem in machine learning and information retrieval where one is given a collection of feature vectors that represent data such as documents or images. The volume of a collection of vectors is used as a measure of their diversity, and partition or matroid constraints over [m] are imposed in order to ensure resource or fairness constraints. Even with a simple cardinality constraint (B = ([m] r), the problem becomes NP-hard and has received much attention starting with a result by Khachiyan [J. Complexity, 11 (1995) pp. 138--153] who gave an rO(r) approximation algorithm for a special case of this problem. Recently, Nikolov and Singh [Proceedings of the Forty-eighth Annual ACM Symposium on Theory of Computing, 2016, pp. 192-- 201] presented a convex program and showed how it can be used to estimate the value of the most diverse set when there are multiple cardinality constraints (i.e., when \scrB corresponds to a partition matroid). Their proof of the integrality gap of the convex program relied on an inequality by Gurvits [Proceedings of the Thirty-eighth Annual ACM Symposium on Theory of Computing, ACM, 2006, pp. 417--426], and was recently extended to regular matroids [Straszak and Vishnoi, Proceedings of the Forty-ninth ACM SIGACT Symposium on Theory of Computing, 2017, pp. 370--383] and [Anaris and Gharan, Proceedings of the Forty-ninth Annual SIGACT Symposium on Theory of Computing, 2017, pp. 384--396] and general matroids [Anari, Gharan, and Vinzant, Proceedings of the Fifty-ninth IEEE Annual Symposium on Foundations of Computer Science, 2018, pp. 35-- 46]. The question of whether these estimation algorithms can be converted into the more useful approximation algorithms--that also output a set--remained open. The main contribution of this paper is to give the first approximation algorithms for both partition and regular matroids. We present novel formulations for the subdeterminant maximization problem, for these matroids; this reduces them to the problem of finding a point that maximizes the absolute value of a nonconvex function over a Cartesian product of probability simplices. The technical core of our results is a new anti-concentration inequality for dependent random variables that arise from these functions, which allows us to relate the optimal value of these nonconvex functions to their value at a random point. Unlike prior work on the constrained subdeterminant maximization problem, our proofs do not rely on real-stability or convexity and could be of independent interest both in algorithms and complexity where anti-concentration phenomena have recently been deployed. [ABSTRACT FROM AUTHOR]

Sparse regression and variable selection for large-scale data have been rapidly developed in the past decades. This work focuses on sparse ridge regression, which enforces the sparsity by use of the L0 norm. We first prove that the continuous relaxation of the mixed integer second order conic (MISOC) reformulation using perspective formulation is equivalent to that of the convex integer formulation proposed in recent work. We also show that the convex hull of the constraint system of the MISOC formulation is equal to its continuous relaxation. Based upon these two formulations (i.e., the MISOC formulation and convex integer formulation), we analyze two scalable algorithms, the greedy and randomized algorithms, for sparse ridge regression with desirable theoretical properties. The proposed algorithms are proved to yield near-optimal solutions under mild conditions. We further propose integrating the greedy algorithm with the randomized algorithm, which can greedily search the features from the nonzero subset identified by the continuous relaxation of the MISOC formulation. The merits of the proposed methods are illustrated through numerical examples in comparison with several existing ones. [ABSTRACT FROM AUTHOR]

We introduce reroutable flows, a robust version of network flows in which link failures can be mitigated by rerouting the affected flow. An important new feature of this model, distinguishing it from existing robust network flow models, is that no flow can get lost in the network. Our goal is to compute maximum flows under this robustness requirement. We investigate different variants depending on the number of failing links, the capacities available for rerouting, and integrality requirements. While the most general versions of the model turn out to be NP-hard, we devise linear programming (LP) formulations and combinatorial algorithms for important special cases and provide approximation algorithms for the harder variants. [ABSTRACT FROM AUTHOR]

We consider questions that arise from the intersection between the areas of polynomial-time approximation algorithms, subexponential-time algorithms, and fixed-parameter tractable (FPT) algorithms. The questions, which have been asked several times, are whether there is a nontrivial FPT-approximation algorithm for the Maximum Clique (Clique) and Minimum Dominating Set (DomSet) problems parameterized by the size of the optimal solution. In particular, letting OPT be the optimum and N be the size of the input, is there an algorithm that runs in t(OPT)poly(N) time and outputs a solution of size f(OPT) for any computable functions t and f that are independent of N (for Clique, we want f (OPT) = omega(1))? In this paper, we show that both Clique and DomSet admit no nontrivial FPT-approximation algorithm, i.e., there is no o(OPT)-FPT-approximation algorithm for Clique and no f (OPT)-FPT-approximation algorithm for DomSet for any function f. In fact, our results imply something even stronger: The best way to solve Clique and DomSet, even approximately, is to essentially enumerate all possibilities. Our results hold under the Gap Exponential Time Hypothesis [I. Dinur. ECCC, TR16-128, 2016; P. Manurangsi and P. Raghavendra, preprint, arXiv:1607.02986, 2016], which states that no 2(o(n))-time algorithm can distinguish between a satisfiable 3 SAT formula and one which is not even (1 - epsilon)-satisfiable for some constant epsilon > 0. Besides Clique and DomSet, we also rule out nontrivial FPT-approximation for the Maximum Biclique problem, the problem of finding maximum subgraphs with hereditary properties (e.g., Maximum Induced Planar Subgraph), and Maximum Induced Matching in bipartite graphs, and we rule out the k(o(1))-FPT-approximation algorithm for the Densest k-Subgraph problem. [ABSTRACT FROM AUTHOR]

We study approximation algorithms for problems of scheduling precedence constrained jobs with the objective of minimizing total weighted completion time, in identical and related machine models. We give algorithms that improve upon many previous 15- to 20-year-old state-of-the-art results. A major theme in these results is the use of time-indexed linear programming relaxations, which are quite natural for their respective problems. We also consider the scheduling problem of minimizing total weighted completion time on unrelated machines. The recent breakthrough result of [N. Bansal, A. Srinivasan, and O. Svensson, in Proceedings of the 48th Annual ACM Symposium on Theory of Computing, ACM, 2016, pp. 156-167] gave a (1.5 c)-approximation for the problem, based on a two-round lift-and-project of the SDP relaxation for the problem. Our main result is that a (1.5 c)-approximation can also be achieved using a natural and considerably simpler time-indexed linear programming relaxation for the problem. We hope this relaxation can provide new insights into the problem. [ABSTRACT FROM AUTHOR]

Clustering is a classic topic in optimization with k-means being one of the most fundamental such problems. In the absence of any restrictions on the input, the best known algorithm for k-means with a provable guarantee is a simple local search heuristic yielding an approximation guarantee of 9+ϵ, a ratio that is known to be tight with respect to such methods. We overcome this barrier by presenting a new primal-dual approach that allows us to (1) exploit the geometric structure of k-means and (2) to satisfy the hard constraint that at most k clusters are selected without deteriorating the approximation guarantee. Our main result is a 6.357-approximation algorithm with respect to the standard LP relaxation. Our techniques are quite general and we also show improved guarantees for the general version of k-means where the underlying metric is not required to be Euclidean and for k-median in Euclidean metrics. [ABSTRACT FROM AUTHOR]

We study the problem of approximating the number of k-cliques in a graph when given query access to the graph. We consider the standard query model for general graphs via (1) degree queries, (2) neighbor queries and (3) pair queries. Let n denote the number of vertices in the graph, m the number of edges, and Ck the number of k-cliques. We design an algorithm that outputs a (1+ε)-approximation (with high probability) for Ck, whose expected query complexity and running time are .... Hence, the complexity of the algorithm is sublinear in the size of the graph for Ck=ω(mk/2-1). Furthermore, we prove a lower bound showing that the query complexity of our algorithm is essentially optimal (up to the dependence on logn, 1/ε and k). The previous results in this vein are by Feige (SICOMP 06) and by Goldreich and Ron (RSA 08) for edge counting (k=2) and by Eden et al. (FOCS 2015) for triangle counting (k=3). Our result matches the complexities of these results. The previous result by Eden et al. hinges on a certain amortization technique that works only for triangle counting, and does not generalize for larger cliques. We obtain a general algorithm that works for any k≥3 by designing a procedure that samples each k-clique incident to a given set S of vertices with approximately equal probability. The primary difficulty is in finding cliques incident to purely high-degree vertices, since random sampling within neighbors has a low success probability. This is achieved by an algorithm that samples uniform random high degree vertices and a careful tradeoff between estimating cliques incident purely to high-degree vertices and those that include a low-degree vertex. [ABSTRACT FROM AUTHOR]

We describe approximation algorithms in Linial's classic LOCAL model of distributed computing to find maximum-weight matchings in a hypergraph of rank r. Our main result is a deterministic algorithm to generate a matching which is an O(r)-approximation to the maximum weight matching, running in Õ(r log Δ + log² Δ + log* n) rounds. (Here, the Õ() notations hides polyloglog Δ and polylog r factors). This is based on a number of new derandomization techniques extending methods of Ghaffari, Harris & Kuhn (2017). The first main application is to nearly-optimal algorithms for the long-studied problem of maximum-weight graph matching. Specifically, we get a (1+ε) approximation algorithm using Õ(log Δ/ε³ + polylog(1/ε, log log n)) randomized time and Õ(log² Δ/ε 4 + log*n/ε) deterministic time. The second application is a faster algorithm for hypergraph maximal matching, a versatile subroutine introduced in Ghaffari et al. (2017) for a variety of local graph algorithms. This gives an algorithm for (2Δ - 1) -edge-list coloring in Õ(log² Δ log n) rounds deterministically or Õ((log log n)³) rounds randomly. Another consequence (with additional optimizations) is an algorithm which generates an edge-orientation with out-degree at most ⌈(1+ε)λ⌉ for a graph of arboricity λ; for fixed ε this runs in Õ(log 6 n) rounds deterministically or Õ(log³ n) rounds randomly. [ABSTRACT FROM AUTHOR]

We design and implement an efficient parallel algorithm for finding a perfect matching in a weighted bipartite graph such that weights on the edges of the matching are large. This problem differs from the maximum weight matching problem, for which scalable approximation algorithms are known. It is primarily motivated by finding good pivots in scalable sparse direct solvers before factorization. Due to the lack of scalable alternatives, distributed solvers use sequential implementations of maximum weight perfect matching algorithms, such as those available in MC64. To overcome this limitation, we propose a fully parallel distributed memory algorithm that first generates a perfect matching and then iteratively improves the weight of the perfect matching by searching for weight-increasing cycles of length 4 in parallel. For most practical problems the weights of the perfect matchings generated by our algorithm are very close to the optimum. An efficient implementation of the algorithm scales up to 256 nodes (17,408 cores) on a Cray XC40 supercomputer and can solve instances that are too large to be handled by a single node using the sequential algorithm. [ABSTRACT FROM AUTHOR]

The stability and error analysis of a second-order fast approximation are considered for the one-dimensional local and nonlocal diffusion equations in the unbounded spatial domain. We first use the conventional central difference scheme to discretize the local second-order spatial derivative operator and use an asymptotically compatible difference scheme to discretize the spatial nonlocal diffusion operator, and apply second-order backward differentiation formula (BDF2) to approximate the temporal derivative to achieve a fully discrete infinity system. To solve the resulting fully discrete systems, we develop a unified framework that is applicable to the discretization of both local and nonlocal problems. A key ingredient is to derive Dirichlet-to-Neumann (DtN)-type absorbing boundary conditions (ABCs). To do so, we apply the z-transform and solve an exterior problem using an iteration technique to derive a Dirichlet-to-Dirichlet (DtD)-type mapping as exact ABCs. After that, we use the Green formula to reformulate the DtD-type mapping equivalently as the DtN-type mapping. The resulting DtN-type mapping allows us to reduce the infinity discrete system into a finite discrete system in a truncated computational domain of interest, and also make it possible to present the stability and convergence analysis of the reduced problem under some open but reasonable assumptions. To efficiently implement the exact ABCs, we further develop a fast convolution algorithm based on approximation of the contour integral induced by the inverse z-transform. The stability and error analysis of the reduced finite discrete system based on the fast algorithm for exact ABCs are also established, and numerical examples are provided to demonstrate the effectiveness of our proposed approach. [ABSTRACT FROM AUTHOR]

This paper considers minimizing the lk-norms of flow time on a single machine offline using a preemptive scheduler for k ≥ 1. The objective is ideal for optimizing jobs' overall waiting times while simultaneously being fair to individual jobs. This work gives the first O(1)-approximation for the problem, improving upon the previous best O(log log P)-approximation by Bansal and Pruhs (FOCS 09 and SICOMP 14) where P is the ratio of the maximum job size to the minimum. The main technical ingredient used in this work is a novel combination of quasi-uniform sampling and iterative rounding, which is of interest in its own right. [ABSTRACT FROM AUTHOR]

For any constant d and parameter ε ∈(0, 1/2], we show the existence of (roughly) 1/ εd orderings on the unit cube [0, 1)d such that for any two points p, q ∈ [0, 1)d close together under the Euclidean metric, there is a linear ordering in which all points between p and q in the ordering are ``close"" to p or q. More precisely, the only points that could lie between p and q in the ordering are points with Euclidean distance at most ε ||p - q|| from either p or q. These orderings are extensions of the Z-order, and they can be efficiently computed. Functionally, the orderings can be thought of as a replacement to quadtrees and related structures (like well-separated pair decompositions). We use such orderings to obtain surprisingly simple algorithms for a number of basic problems in lowdimensional computational geometry, including (i) dynamic approximate bichromatic closest pair, (ii) dynamic spanners, (iii) dynamic approximate minimum spanning trees, (iv) static and dynamic fault-tolerant spanners, and (v) approximate nearest neighbor search. [ABSTRACT FROM AUTHOR]

In this paper, we provide the first provable linear-time (in terms of the number of nonzero entries of the input) algorithm for approximately solving the generalized trust region subproblem (GTRS) of minimizing a quadratic function over a quadratic constraint under some regularity condition. Our algorithm is motivated by and extends a recent linear-time algorithm for the trust region subproblem by Hazan and Koren [Math. Program., 158 (2016), pp. 363–381]. However, due to the nonconvexity and noncompactness of the feasible region, such an extension is nontrivial. Our main contribution is to demonstrate that under some regularity condition, the optimal solution is in a compact and convex set and lower and upper bounds of the optimal value can be computed in linear time. Using these properties, we develop a linear-time algorithm for the GTRS. [ABSTRACT FROM AUTHOR]

Motivated by emerging resource allocation and data placement problems such as web caches and peer-to-peer systems, we consider and study a class of resource allocation problems over a network of agents (nodes). In this model, which can be viewed as a homogeneous data placement problem, nodes can store only a limited number of resources while accessing the remaining ones through their closest neighbors. We consider this problem under both optimization and gametheoretic frameworks. In the case of optimal resource allocation, we will first show that when there are only k = 2 resources, the optimal allocation can be found efficiently in O(n ² log n) steps, where n denotes the total number of nodes. However, for k \geq 3 this problem becomes NP-hard with no polynomial-time approximation algorithm with a performance guarantee better than 1 + 1 102k², even under metric access costs. We then provide a 3-approximation algorithm for the optimal resource allocation which runs only in O(kn² ). Subsequently, we look at this problem under a selfish setting formulated as a noncooperative game and provide a 3-approximation algorithm for obtaining its pure Nash equilibria under metric access costs. We then establish an equivalence between the set of pure Nash equilibria and flip-optimal solutions of the Max-k-Cut problem over a specific weighted complete graph. While this reduction suggests that finding a pure Nash equilibrium using best response dynamics might be PLS-hard, it allows us to use tools from complementary slackness and quadratic programming to devise systematic and more efficient algorithms towards obtaining Nash equilibrium points. [ABSTRACT FROM AUTHOR]

We study partial and budgeted versions of the well-studied connected dominating set problem. In the partial connected dominating set (PCDS) problem, we are given an undirected graph G = (V, E) and an integer n, and the goal is to find a minimum subset of vertices that induces a connected subgraph of G and dominates at least nvertices. We obtain the first polynomial time algorithm with an O(ln ?) approximation guarantee for this problem, thereby significantly extending the results of Guha and Khuller [Algorithmica, 20(1998), pp. 374--387] for the connected dominating set problem. We note that none of the methods developed earlier can be applied directly to solve this problem. In the budgeted connected dominating set problem, there is a budget on the number of vertices we can select, and the goal is to dominate as many vertices as possible. We obtain a 11 (1- e) approximation algorithm for this problem. Finally, we show that our techniques extend to a more general setting where the profit function associated with a subset of vertices is a "special" submodular function. This generalization captures the connected dominating set problem with capacities and/or weighted profits as special cases. This implies an O(ln q) approximation (where q denotes the quota) and O(1) approximation algorithms for the partial and budgeted versions of these problems. While the algorithms are simple, the results make a surprising use of the greedy set cover framework in defining a useful profit function. Finally, we prove that (both edge and node) weighted versions of the PCDS problem are as hard as the more general group Steiner tree problem. [ABSTRACT FROM AUTHOR]

We develop constant-factor approximation algorithms for minimizing the execution time of a coordinated parallel motion plan for a relatively dense swarm of homogeneous robots in the absence of obstacles. In our first model, each robot has a specified start and destination on the square grid, and in each round of coordinated parallel motion, every robot can move to any adjacent position that is either empty or simultaneously being vacated by another robot. In this model, our algorithm achieves constant stretch factor: if every robot starts at distance at most d from its destination, then the total duration of the overall schedule is O(d), which is optimal up to constant factors. Our result holds for distinguished robots (each robot has a specific destination), identical (unlabeled) robots, and most generally, classes of different robot types (where each destination specifies a required type of robot). We also show that finding the optimal coordinated parallel motion plan is NP-hard, justifying approximation algorithms. In our second model, each robot is a unit-radius disk in the plane, and robots can translate continuously in parallel subject to not intersecting, i.e., having disk centers at L2-distance at least 2. We prove the same result--constant-factor approximation algorithm to minimizing execution time via constant stretch factor---when the pairwise L∞ -distance between disk centers is at least 2√ 2 = 2.8284 . . . . On the other hand, for N densely packed disks at distance at most 2 + δ for a sufficiently small δ > 0, we prove that a stretch factor of Ω(N1/4) is sometimes necessary (when densely packed), while a stretch factor of O (N1/2) is always possible. [ABSTRACT FROM AUTHOR]

An instance of the constraint satisfaction problem (CSP) is given by a family of constraints on overlapping sets of variables, and the goal is to assign values from a fixed domain to the variables so that all constraints are satisfied. In the optimization version, the goal is to maximize the number of satisfied constraints. An approximation algorithm for a CSP is called robust if it outputs an assignment satisfying an (1 - g(ε))-fraction of constraints on any (1 - ε )- satisfiable instance, where the loss function g is such that g(ε ) \rightarrow 0 as ε \rightarrow 0. We study how the robust approximability of CSPs depends on the set of constraint relations allowed in instances, the so-called constraint language. All constraint languages admitting a robust polynomial-time algorithm (with some g) have been characterized by Barto and Kozik, with the general bound on the loss g being doubly exponential, specifically g(ε ) = O((log log(1/ε ))/ log(1/ε)). It is natural to ask when a better loss can be achieved, in particular polynomial loss g(ε ) = O(ε 1/k) for some constant k. In this paper, we consider CSPs with a constraint language having a near-unanimity polymorphism. This general condition almost matches a known necessary condition for having a robust algorithm with polynomial loss. We give two randomized robust algorithms with polynomial loss for such CSPs: one works for any near-unanimity polymorphism and the parameter k in the loss depends on the size of the domain and the arity of the relations in Γ, while the other works for a special ternary near-unanimity operation called the dual discriminator with k = 2 for any domain size. In the latter case, the CSP is a common generalization of Unique Games with a fixed domain and 2-Sat. In the former case, we use the algebraic approach to the CSP. Both cases use the standard semidefinite programming relaxation for the CSP [ABSTRACT FROM AUTHOR]

Let S be a set of n points on a polyhedral terrain T in R³, and let ε > 0 be a fixed constant. We prove that S admits a (2 + ε)-spanner with O(n log n) edges with respect to the geodesic distance. This is the first spanner with constant spanning ratio and a near-linear number of edges for points on a terrain. On our way to this result, we prove that any set of n weighted points in \BbbR d admits an additively weighted (2 + ε)-spanner with O(n) edges; this improves the previously best known bound on the spanning ratio (which was 5 + ε) and almost matches the lower bound. [ABSTRACT FROM AUTHOR]

The MaxCut approximation algorithm by Goemans and Williamson is one of the most celebrated results in semidefinite optimization, and the corresponding MaxCut semidefinite optimization problem (SDP) has many favourable properties. The feasible regions of this class of SDPs are known as elliptopes, and they have been studied extensively. One of their nicest geo-metric/duality properties is the fact that their vertices correspond exactly to the cuts of a graph, as proved by Laurent and Poljak in 1995. Recall that a boundary pointx of a convex set C is called a vertex of C if the normal cone of C at x is full-dimensional. Semidefinite programs over elliptopes were also exploited by Goemans and Williamson and by Nesterov to develop approximation algorithms for the Maximum-2-Satisfiability problem and for nonconvex quadratic optimization problems, respectively. We study how often strict complementarity holds or fails for SDPs over elliptopes when a vertex is optimal, i.e., when the SDP relaxation is tight. While strict complementarity is known to hold when the objective function is in the interior of the normal cone at any vertex, we prove that it fails generically (in a context of Hausdorff measure and Hausdorff dimension) at the boundary of such normal cones. In this regard, SDPs over elliptopes display the nastiest behavior possible for a convex optimization problem. We also study strict complementarity with respect to two classes of objective functions. We show that, when the objective functions are sampled uniformly from a class of negative semidefinite rank-one matrices in the boundary of the normal cone at any vertex, the probability that strict complementarity holds lies in (0,1). To complete our study with a spectral-graph-theory-based viewpoint of the data for the MaxCut SDP, we extend a construction due to Laurent and Poljak of weighted Laplacian matrices for which strict complementarity fails. Their construction works for complete graphs, and we extend it to cosums of graphs under some mild conditions. [ABSTRACT FROM AUTHOR]

Kernel methods are widespread in machine learning; however, they are limited by the quadratic complexity of the construction, application, and storage of kernel matrices. Low-rank matrix approximation algorithms are widely used to address this problem and reduce the arithmetic and storage cost. However, we observed that for some datasets with wide intraclass variability, the optimal kernel parameter for smaller classes yields a matrix that is less well-approximated by low-rank methods. In this paper, we propose an efficient structured low-rank approximation method|the block basis factorization (BBF)|and its fast construction algorithm to approximate radial basis function kernel matrices. Our approach has linear memory cost and oating point operations for many machine learning kernels. BBF works for a wide range of kernel bandwidth parameters and extends the domain of applicability of low-rank approximation methods significantly. Our empirical results demonstrate the stability and superiority over the state-of-the-art kernel approximation algorithms. [ABSTRACT FROM AUTHOR]

We consider the integrality gap of the subtour linear program (LP) relaxation of the traveling salesman problem (TSP) restricted to circulant instances. De Klerk and Dobre [Discrete Appl. Math., 159 (2011), pp. 1815--1826] conjectured that the value of the optimal solution to the subtour LP in these instances is equal to an entirely combinatorial lower bound from Van der Veen, Van Dal, and Sierksma [The Symmetric Circulant Traveling Salesman Problem, Research Memorandum 429, Institute of Economic Research, University of Groningen, 1991]. We prove this conjecture by giving an explicit optimal solution to the subtour LP. We then show that the integrality gap of the subtour LP is 2 on circulant instances, making such instances one of the few nontrivial classes of TSP instances for which the integrality gap of the subtour LP is exactly known. We also show that the degree constraints do not strengthen the subtour LP on circulant instances, mimicking the parsimonious property of metric, symmetric TSP instances shown in Goemans and Bertsimas [Math. Programming, 60 (1993), pp. 145--166] in a distinctly nonmetric set of instances. [ABSTRACT FROM AUTHOR]

We revisit the classic problem of estimating the moments of the degree distribution of an undirected simple graph. Consider an undirected simple graph G = (V,E) with n (nonisolated) vertices, and define (for s > 0) Ms =\sum v\in V ds v. Our aim is to estimate Ms within a multiplicative error of (1 +\varepsilon) (for a given approximation parameter\varepsilon > 0) in sublinear time. We consider the sparse-graph model that allows access to uniform random vertices, queries for the degree of any vertex, and queries for a neighbor of any vertex. For the case of s = 1 (the average degree), O\ast (\surd n) queries suffice for any constant\varepsilon [U. Feige, SIAM J. Comput., 35 (2006), pp. 964--984], [O. Goldreich and D. Ron, Random Structures Algorithms, 32 (2008), pp. 473--493]. (We use the O\ast notation to suppress dependencies in log n and 1/\varepsilon.) Gonen, Ron, and Shavitt [SIAM J. Discrete Math., 25 (2011), pp. 1365--1411] extended this result to all integral s > 0 by designing an algorithm that performs O\ast (n1 1/(s+1)) queries. (Strictly speaking, their algorithm approximates the number of star-subgraphs of a given size, but a slight modification gives an algorithm for moments.) We design a new, significantly simpler algorithm for this problem. In the worst case, it exactly matches the bounds of Gonen, Ron, and Shavitt and has a much simpler proof. More importantly, the running time of this algorithm is connected to the arboricity of G. This is (essentially) the maximum density of an induced subgraph. For the family of graphs with arboricity at most\alpha, it has a query complexity of O\ast\bigl(n\cdot\alpha 1/s M 1/s s + min\bigl\{ m M 1/s s, m\cdot ns 1 Ms\bigr\}\bigr) which is always upper bounded by O\ast\bigl(n\alpha M 1/s s\bigr). Thus, for the class of constant-arboricity graphs (which includes, among others, all minor-closed families and preferential attachment graphs), we can estimate the average degree in O\ast (1) queries, and we can estimate the variance of the degree distribution in O\ast (\surd n) queries. This is a major improvement over the previous worst-case bounds. [ABSTRACT FROM AUTHOR]

We study the restricted case of Scheduling on Unrelated Parallel Machines. In this problem, we are given a set of jobs J with processing times pj and each job may be scheduled only on some subset of machines Sj⊆ M. The goal is to find an assignment of jobs to machines to minimize the time within which all jobs can be processed. In a seminal paper, Lenstra, Shmoys, and Tardos [Proceedings of the 28th Annual IEEE Conference on Foundations of Computer Science, 1987, pp. 217--224] designed an elegant 2-approximation for the problem. The question of whether approximation algorithms with better guarantees exist for this classic scheduling problem has since remained a source of mystery. In recent years, with the improvement of our understanding of configuration linear programs, it now appears an attainable goal to design such an algorithm. Our main contribution in this paper is to make progress towards this goal. For the so-called (1, ε)-case, when the processing times of jobs are either 1 or ε ∊ (0, 1), we design an approximation algorithm whose guarantee tends to 1+√3/2 ≈ 1.866025 as ε tends to zero. This improves on the 2 ε0 guarantee recently obtained by Chakrabarty, Khanna, and Li [Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 2015, pp. 1087--1101] for some constant ε0 > 0. Further, the ideas presented in this paper do not crucially depend on the fact that the instances contain exactly two different job sizes; i.e., they extend also to families of instances more general than the (1, ε)-case. In a certain precise sense, we fall slightly short of improving on the 30-year-old classic algorithm of Lenstra, Shmoys, and Tardos [Proceedings of the 28th Annual IEEE Conference on Foundations of Computer Science, 1987, pp. 217--224] for the restricted case. [ABSTRACT FROM AUTHOR]

We consider the maximization problem of monotone submodular functions under an uncertain knapsack constraint. Specifically, the problem is discussed in the situation where the knapsack capacity is not given explicitly and can be accessed only through an oracle that answers whether or not the current solution is feasible when an item is added to the solution. Assuming that cancellation of the last item is allowed when it overflows the knapsack capacity, we discuss the robustness ratios of adaptive policies for this problem, which are the worst case ratios of the objective values achieved by the output solutions to the optimal objective values. We present a randomized policy of robustness ratio (1 1/e)/2 and a deterministic policy of robustness ratio 2(1 1/e)/21. We also consider a universal policy that chooses items following a precomputed sequence. We present a randomized universal policy of robustness ratio (1 1/ 4 \surd e)/2. When cancellation is not allowed, no randomized adaptive policy achieves a constant robustness ratio. Because of this hardness, we assume that a probability distribution of the knapsack capacity is given, and we consider computing a sequence of items that maximizes the expected objective value. We present a polynomial time randomized algorithm of approximation ratio (1 1/ 4 \surd e)/4 \epsilon for any small constant \epsilon > 0. [ABSTRACT FROM AUTHOR]

We consider the problem of maximizing a monotone submodular function under a knapsack constraint. We show that, for any fixed ϵ>0, there exists a polynomial-time algorithm with an approximation ratio 1-c/e-ϵ, where c∈[0,1] is the (total) curvature of the input function. This approximation ratio is tight up to ϵ for any c∈[0,1]. To the best of our knowledge, this is the first result for a knapsack constraint that incorporates the curvature to obtain an approximation ratio better than 1-1/e, which is tight for general submodular functions. As an application of our result, we present a polynomial-time algorithm for the budget allocation problem with an improved approximation ratio. [ABSTRACT FROM AUTHOR]

This paper presents a weakly intrusive strategy for computing a low-rank approximation of the solution of a system of nonlinear parameter-dependent equations. The proposed strategy relies on a Newton-like iterative solver which only requires evaluations of the residual of the parameter-dependent equation and of a preconditioner (such as the differential of the residual) for instances of the parameters independently. The algorithm provides an approximation of the set of solutions associated with a possibly large number of instances of the parameters, with a computational complexity which can be orders of magnitude lower than when using the same Newton-like solver for all instances of the parameters. The reduction of complexity requires efficient strategies for obtaining low-rank approximations of the residual, of the preconditioner, and of the increment at each iteration of the algorithm. For the approximation of the residual and the preconditioner, weakly intrusive variants of the empirical interpolation method are introduced, which require evaluations of entries of the residual and the preconditioner. Then, an approximation of the increment is obtained by using a greedy algorithm for low-rank approximation, and a low-rank approximation of the iterate is finally obtained by using a truncated singular value decomposition. When the preconditioner is the differential of the residual, the proposed algorithm is interpreted as an inexact Newton solver for which a detailed convergence analysis is provided. Numerical examples illustrate the efficiency of the method. [ABSTRACT FROM AUTHOR]

We propose a fully polynomial-time approximation scheme (FPTAS) for stochastic dynamic programs with multidimensional action, scalar state, convex costs, and linear state transition function. The action spaces are polyhedral and described by parametric linear programs. This type of problem finds applications in the area of optimal planning under uncertainty, and can be thought of as the problem of optimally managing a single nondiscrete resource over a finite time horizon. We show that under a value oracle model for the cost functions this result for one-dimensional state space is the “best possible,” because a similar dynamic programming model with two-dimensional state space does not admit a polynomial-time approximation scheme. The FPTAS relies on the solution of polynomial-sized linear programs to recursively compute an approximation of the value function at each stage. Our paper enlarges the class of dynamic programs that admit an FPTAS by showing, under suitable conditions, how to deal with multidimensional action spaces and with vectors of continuous random variables with bounded support. These results bring us one step closer to overcoming the curse of dimensionality of dynamic programming. [ABSTRACT FROM AUTHOR]

Implicit Euler approximations of the equations governing the porous flow of two immiscible incompressible fluids are shown to be the Euler-Lagrange equations of a convex function. Tools from convex analysis are then used to develop robust fully discrete algorithms for their numerical approximation. Existence and uniqueness of solutions to control volume approximations are established. [ABSTRACT FROM AUTHOR]

In this paper we consider the output consensus problem of networked Hammerstein and Wiener systems in a noisy environment. The Hammerstein and Wiener systems are assumed to be open-loop stable, and its static nonlinearity is allowed to grow up no faster than a polynomial. A control algorithm based on the distributed stochastic approximation algorithm with expanding truncations is designed and it is shown that under the designed control the output consensus is achieved. The numerical simulation given in the paper justifies the theoretical assertions. [ABSTRACT FROM AUTHOR]

In this paper, we show that every (2P2, K4)-free graph is 4-colorable. The bound is attained by the five-wheel and the complement of the seven-cycle. This answers an open question by Wagon [J. Combin. Theory Ser. B, 29 (1980), pp. 345-346] from the 1980s. Our result can also be viewed as a result in the study of the Vizing bound for graph classes. A major open problem in the study of computational complexity of graph coloring is whether coloring can be solved in polynomial time for (4P1,C4)-free graphs. Lozin and Malyshev [Discrete Appl. Math., 216 (2017), pp. 273-280] conjecture that the answer is yes. As an application of our main result, we provide the first positive evidence to the conjecture by giving a 2-approximation algorithm for coloring (4P1,C4)-free graphs. [ABSTRACT FROM AUTHOR]