Search

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]

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 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]

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]

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]

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 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 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]

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 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 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 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]

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]

We present several approximation algorithms for the problem of embedding metric spaces into a line, and into the 2-dimensional plane. Among other results, we give an O(√n)- approximation algorithm for the problem of finding a line embedding of a metric induced by a given unweighted graph, that minimizes the (standard) multiplicative distortion. We give an improved Õ(n1/3) approximation for the case of metrics induced by unweighted trees. [ABSTRACT FROM AUTHOR]

We study the mathematical concept of the strength of a graph as defined by Cunningham to partition very large graphs. The strength is the objective value of an attack problem on a graph where the striker aims at dividing the graph into a maximum number of connected components removing as few edges as possible per component uncoupled. The strength is the optimal number of edges per component uncoupled or, in the weighted version, the sum of the weights of the edges removed per component uncoupled. Given a connected graph with n vertices and m weighted edges, we denote by W the total sum of the integer weights, and we describe an algorithm that approximates within a factor of 1+ε the weighted strength in time O(mlog(W)log³(n)/ε²), and that can be implemented with O(m) memory use if we allow a complexity of O(mlog²(W)log³(n)/ε²). This result has several important applications, in particular for the detection of dense areas of a graph, in terms of weighted edges, which in turn can be used for spam detection, community identification, and partitioning. [ABSTRACT FROM AUTHOR]

The Chordal Vertex Deletion (CHVD) problem asks to delete a minimum number of vertices from an input graph to obtain a chordal graph. In this paper we develop a polynomial kernel for CHVD under the parameterization by the solution size. Using a new Erdõs-Pósa-type packing/covering duality for holes in nearly chordal graphs, we present a polynomial-time algorithm that reduces any instance (G, k) of CHVD to an equivalent instance with poly(k) vertices. The existence of a polynomial kernel answers an open problem posed by Marx in 2006 [D. Marx, "Chordal Deletion Is Fixed-Parameter Tractable," in Graph-Theoretic Concepts in Computer Science, Lecture Notes in Comput. Sci. 4271, Springer, 2006, pp. 37-48]. To obtain the kernelization, we develop the first poly(opt)-approximation algorithm for CHVD, which is of independent interest. In polynomial time, it either decides that G has no chordal deletion set of size k, or outputs a solution of size O(k4log² k). [ABSTRACT FROM AUTHOR]

We study scheduling problems on a machine with varying speed. Assuming a known speed function we ask for a cost-efficient scheduling solution. Our main result is a polynomial-time approximation scheme (PTAS) for minimizing the total weighted completion time in this setting. This also implies a PTAS for the closely related problem of scheduling to minimize generalized global cost functions, that is, the problem 1||wjf(Cj). The key to our results is a reinterpretation of the problem within the well-known two-dimensional Gantt chart: instead of the standard approach of scheduling in the time dimension, we construct scheduling solutions in the weight dimension. This allows structural simplifications of the instance and optimal solutions, based on which we can defer the concern of speed to the evaluation of cost in a dynamic programming framework. We also consider a dynamic problem variant, where the decision upon the speed is part of the problem and we are interested in the trade-off between scheduling cost and speed-scaling cost, which is typically the energy consumption. We observe that the optimal order is independent of the energy consumption and that the problem can be reduced to the setting where the speed of the machine is fixed, and thus admits a PTAS. Furthermore, we provide a fully polynomial-time approximation scheme for the NPhard problem variant in which the machine can run only at a fixed number of discrete speeds. Finally, we show how our results can be used to obtain a (2 + ε)-approximation for scheduling preemptive jobs with release dates on multiple identical parallel machines. [ABSTRACT FROM AUTHOR]

We present improved approximation algorithms in stochastic optimization. We prove that the multistage stochastic versions of covering integer programs (such as set cover and vertex cover) admit essentially the same approximation algorithms as their standard (nonstochastic) coun- terparts; this improves upon work of Swamy and Shmoys which shows an approximability that de- pends multiplicatively on the number of stages. We also present approximation algorithms for facility location and some of its variants in the 2-stage recourse model, improving on previous approximation guarantees. We give a 2:2975-approximation algorithm in the standard polynomial-scenario model and an algorithm with an expected per-scenario 2:4957-approximation guarantee, which is applicable to the more general black-box distribution model. [ABSTRACT FROM AUTHOR]

We present a 10/7 -approximation algorithm for the minimum 2-vertex-connected spanning subgraph problem. Similarly to the work of Cheriyan, Sebö, and Szigeti for 2-edge-connected spanning subgraphs, our algorithm is based on computing a carefully designed ear-decomposition. [ABSTRACT FROM AUTHOR]

Given an undirected graph G = (VG,EG) and a fixed "pattern" graph H = (VH,EH) with k vertices, we consider the H-Transversal and H-Packing problems. The former asks to find the smallest S ⊆ VG such that the subgraph induced by VG \ S does not have H as a subgraph, and the latter asks to find the maximum number of pairwise disjoint k-subsets S1,...,Sm ⊆ VG such that the subgraph induced by each Si has H as a subgraph. We prove that if H is 2-connected, H-Transversal and H-Packing are almost as hard to approximate as general k-Hypergraph Vertex Cover and k-Set Packing, so it is NP-hard to approximate them within a factor of Ω(k) and Ω(k), respectively. We also show that there is a 1-connected H where H-Transversal admits an O(log k)-approximation algorithm, so that the connectivity requirement cannot be relaxed from 2 to 1. For a special case of H-Transversal where H is a (family of) cycles, we mention the implication of our result to the related Feedback Vertex Set problem and give a different hardness proof for directed graphs. [ABSTRACT FROM AUTHOR]

We consider the following single-machine scheduling problem, which is often denoted 1||∑ fj: we are given n jobs to be scheduled on a single machine, where each job j has an integral processing time pj, and there is a nondecreasing, nonnegative cost function fj (Cj) that specifies the cost of finishing j at time Cj; the objective is to minimize ∑j=1n fj (Cj). Bansal and Pruhs recently gave the first constant approximation algorithm with a performance guarantee of 16. We improve on this result by giving a primal-dual pseudo-polynomial-time algorithm based on the recently introduced knapsack-cover inequalities. The algorithm finds a schedule of cost at most four times the constructed dual solution. Although we show that this bound is tight for our algorithm, we leave open the question of whether the integrality gap of the linear program is less than 4. Finally, we show how the technique can be adapted to yield, for any ∈ > 0, a polynomial time (4 + ∈)-approximation algorithm for this problem. [ABSTRACT FROM AUTHOR]

Sensor networks are ubiquitously used for detection and tracking and, as a result, covering is one of the main tasks of such networks. We study the problem of maximizing the coverage lifetime of a barrier by mobile sensors with limited battery power, where the coverage lifetime is the time until there is a breakdown in coverage due to the death of a sensor. Sensors are first deployed and then coverage commences. Energy is consumed in proportion to the distance traveled for mobility, while for coverage, energy is consumed in direct proportion to the radius of the sensor raised to a constant exponent. We study two variants which are distinguished by whether the sensing radii are given as part of the input or can be optimized: the fixed radii problem and the variable radii problem. We design parametric search algorithms for both problems for the case where the final order of the sensors is predetermined (e.g., sensors cannot swap locations and the initial order must be preserved) and for the case where sensors are initially located at barrier endpoints. In contrast, we show that the variable radii problem is strongly NP-hard and provide hardness of approximation results for fixed radii for the case where all the sensors are initially colocated at an internal point of the barrier. [ABSTRACT FROM AUTHOR]

We offer a novel classification of voting methods popular in social choice theory. Our classification is based on the more general problem of rank aggregation in which, beyond electing a winner, we also seek to compute an aggregate ranking of all the candidates; moreover, our classification is offered from a computational perspective--based on whether or not the voting method generalizes to an aggregation algorithm guaranteed to produce solutions that are near optimal in minimizing the distance of the aggregate ranking to the voters' rankings with respect to one of three well-known distance measures: the Kendall tau, the Spearman footrule, and the Spearman rho measures. We show that methods based on the average rank of the candidates (Borda counting), on the median rank of the candidates, and on the number of pairwise-majority wins (Copeland) all satisfy the near-optimality criterion with respect to each of these distance measures. On the other hand, we show that natural extensions of each of plurality voting, single transferable voting, and Simpson-Kramer minmax voting do not satisfy the near-optimality criterion with respect to these distance measures. [ABSTRACT FROM AUTHOR]

We study a general class of problems called F-DELETION problems. In an F-DELETION problem, we are asked whether a subset of at most k vertices can be deleted from a graph G such that the resulting graph does not contain as a minor any graph from the family F of forbidden minors. We study the problem parameterized by k, using p-F-DELETION to refer to the parameterized version of the problem. We obtain a number of algorithmic results on the p-F-DELETION problem when F contains a planar graph. We give a linear vertex kernel on graphs excluding t-claw K1,t, the star with t leaves, as an induced subgraph, where t is a fixed integer and an approximation algorithm achieving an approximation ratio of O(log3/2 OPT), where OPT is the size of an optimal solution on general undirected graphs. Finally, we obtain polynomial kernels for the case when F only contains graph θc as a minor for a fixed integer c. The graph θc consists of two vertices connected by c parallel edges. Even though this may appear to be a very restricted class of problems it already encompasses well-studied problems such as VERTEX COVER, FEEDBACK VERTEX SET, and DIAMOND HITTING SET. The generic kernelization algorithm is based on a nontrivial application of protrusion techniques, previously used only for problems on topological graph classes. [ABSTRACT FROM AUTHOR]

Our goal is to show tight bounds on the running time of algorithms for scheduling and packing problems. To prove lower bounds, we investigate implications of the exponential time hypothesis on such algorithms. For exact algorithms we consider the dependence of the running time on the number n of items (for packing) or jobs (for scheduling). We prove a lower bound of 2o(n) x ∥I∥O(n), where ∥I∥ denotes the encoding length of the instance, for several of these problems, including SUBSETSUM, KNAPSACK, BINPACKING, , and . We also develop an algorithmic framework that is able to solve a large number of scheduling and packing problems in time 2o(n) x ∑I∑O(n). Finally, we consider approximation schemes. We show that there is no polynomial time approximation scheme for MULTIPLEKNAPSACK (MKS) and 2D-KNAPSACK with running time 2o(1/ε) x ∑I∑O(n) and no(1/ε) x ∑I∑O(n), respectively. [ABSTRACT FROM AUTHOR]

An identifying code of a graph is a subset of its vertices such that every vertex of the graph is uniquely identified by the set of its neighbors within the code. We show a dichotomy for the size of the smallest identifying code in classes of graphs closed under induced subgraphs. Our dichotomy is derived from the VC-dimension of the considered class C, that is, the maximum VCdimension over the hypergraphs formed by the closed neighborhoods of elements of C. We show that hereditary classes with infinite VC-dimension have infinitely many graphs with an identifying code of size logarithmic in the number of vertices, while classes with finite VC-dimension have a polynomial lower bound. We then turn to approximation algorithms. We show that Min Id Code (the problem of finding a smallest identifying code in a given graph from some class C) is log-APX-hard for any hereditary class of infinite VC-dimension. For hereditary classes of finite VC-dimension, the only known previous results show that we can approximate Min Id Code within a constant factor in some particular classes, e.g., line graphs, planar graphs, and unit interval graphs. We prove that Min Id Code can be approximate within a factor 6 for interval graphs. In contrast, we show that Min Id Code on C4-free bipartite graphs (a class of finite VC-dimension) cannot be approximated to within a factor of c log(|V |) for some c > 0. [ABSTRACT FROM AUTHOR]

We study the metric s-t path traveling salesman problem (TSP). An, Kleinberg, and Shmoys [Proceedings of the 44th ACM Symposium on Theory of Computing, 2012, pp. 875-886] improved on the long-standing 5/3-approximation factor and presented an algorithm that achieves an approximation factor of 1+√5/2 ≈ 1.61803. Later, Sebô [Proceedings of the 16th Conference on Integer Programming and Combinatorial Optimization, 2013, pp. 362-374] further improved the approximation factor to 8/5. We present a simple, self-contained analysis that unifies both results; our main contribution is a unified correction vector. Additionally, we compare two different linear programming (LP) relaxations of the s-t path TSP, namely, the path version of the Held--Karp LP relaxation for the TSP and a weaker LP relaxation, and we show that both LPs have the same (fractional) optimal value. Also, we show that the minimum cost of integral solutions of the two LPs are within a factor of 3/2 of each other. Furthermore, we prove that a half-integral solution of the stronger LP relaxation of cost c can be rounded to an integral solution of cost at most 3/2c. Finally, we give an example that presents obstructions to two natural methods that aim for an approximation factor of 3/2. [ABSTRACT FROM AUTHOR]

Trevisan [SIAM J. Comput., 41 (2012), pp. 1769-1786] presented an algorithm for Max-Cut based on spectral partitioning techniques. This is the first algorithm for Max-Cut with an approximation guarantee strictly larger than 1/2 that is not based on semidefinite programming. Trevisan showed that its approximation ratio is of at least 0.531. In this paper we improve this bound up to 0.614247. We also define and extend this result for the more general maximum colored cut problem. [ABSTRACT FROM AUTHOR]

In this note, we prove that all cop-win graphs G in the game in which the robber and the cop move at different speeds s and s' with s' < s, are < δ-hyperbolic with δ = O(s²). We also show that the dependency between S and s is linear if s - s' = Ω(s) and G obeys a slightly stronger condition. This solves an open question from the paper [J. Chalopin et al., SIAM J. Discrete Math., 25 (2011), pp. 333-359]. Since any δ-hyperbolic graph is cop-win for s = 2r and s' = r + 2δ for any r > 0, this establishes a new--game-theoretical--characterization of Gromov hyperbolicity. We also show that for weakly modular graphs the dependency between δ and s is linear for any s' < s. Using these results, we describe a simple constant-factor approximation of the hyperbolicity δ of a graph on n vertices in O(n²) time when the graph is given by its distance matrix. [ABSTRACT FROM AUTHOR]

Let G = (V, E) be a simple graph of maximum degree Δ. The edges of G can be colored with at most Δ + 1 colors by Vizing's theorem. We study lower bounds on the size of subgraphs of G that can be colored with A colors. Vizing's theorem gives a bound of Δ/Δ + 1 |E|. This is known to be tight for cliques κΔ + 1 when Δ is even. However, for Δ = 3 it was improved to 26/31 |E| by Albertson and Haas [Discrete Math., 148 (1996), pp. 1-7] and later to 6/7|E| by Rizzi [Discrete Math., 309 (2009), pp. 4166-4170]. It is tight for B3, the graph isomorphic to a K4 with one edge subdivided. We improve previously known bounds for Δ ∈ {3,..., 7}, under the assumption that for Δ = 3,4,6, graph G is not isomorphic to B3, K5, and K7, respectively. For Δ ≥ 4 these are the first results which improve over the Vizing's bound. We also show a new bound for subcubic multigraphs not isomorphic to K3 with one edge doubled. In the second part, we give approximation algorithms for the maximum κ-edge-colorable subgraph problem, where given a graph G (without any bound on its maximum degree or other restrictions) one has to find a κ-edge-colorable subgraph with the maximum number of edges. In particular, when G is simple for κ = 3, 4, 5, 6, 7 we obtain approximation ratios of 13/15, 9/11, 19/22, 23/27, and 22/25, respectively. We also present a 7/9-approximation for κ = 3 when G is a multigraph. The approximation algorithms follow from a new general framework that can be used for any value of κ. [ABSTRACT FROM AUTHOR]

The c-pumpkin is the graph with two vertices linked by c ≥ 1 parallel edges. A c-pumpkin-model in a graph G is a pair {A, B} of disjoint subsets of vertices of G, each inducing a connected subgraph of G, such that there are at least c edges in G between A and B. We focus on hitting and packing c-pumpkin-models in a given graph in the realm of approximation algorithms and parameterized algorithms. We give a fixed-parameter tractable (FPT) algorithm running in time 2...(κ)(n...(1) deciding, for any fixed c ≥ 1, whether all c-pumpkin-models can be hit by at most k vertices. This generalizes known single-exponential FPT algorithms for Vertex Cover and Feedback Vertex SET, which correspond to the cases c = 1, 2 respectively. Finally, we present an ...(log n)-approximation algorithm for both the problems of hitting all c-pumpkin-models with a smallest number of vertices and packing a maximum number of vertex-disjoint c-pumpkin-models. [ABSTRACT FROM AUTHOR]

We consider connectivity problems with orientation constraints. Given a directed graph D and a collection of ordered node pairs P let P[D] = {(u, v) ∈ P : D contains a uv-path}. In the Steiner Forest Orientation problem we are given an undirected graph G = (V, E) with edge-costs and a set P ⊆ V x V of ordered node pairs. The goal is to find a minimum-cost subgraph H of G and an orientation D of H such that P[D] = P. We give a 4-approximation algorithm for this problem. In the Maximum Pairs Orientation problem we are given a graph G and a multicollection of ordered node pairs P on V. The goal is to find an orientation D of G such that |P[D]| is maximum. Generalizing the result of Arkin and Hassin [Discrete Appl. Math., 116 (2002), pp. 271-278] for |P| = 2, we will show that for a mixed graph G (that may have both directed and undirected edges), one can decide in nO(|P|) time whether G has an orientation D with P[D] = P. (For undirected graphs this problem admits a polynomial time algorithm for any P, but it is NP-complete on mixed graphs.) For undirected graphs, we will show that one can decide whether G admits an orientation D with |P[D]| ≥ k in O(n + m) + 2O(k · log log k) time; hence this decision problem is fixed-parameter tractable, which answers an open question from Dorn et al. [Algorithms Molecular Biol., 6 (2011)]. We also show that Maximum Pairs Orientation admits ratio O(log |P|/ log log |P|), which is better than the ratio O(log n/ log log n) of Gamzu, Segev, and Sharan [Proceedings of WABI 2010, pp. 215-225] when |P| < n. [ABSTRACT FROM AUTHOR]

Given nf sites, each equipped with one facility, and nc cities, fault tolerant facility location (FTFL) [K. Jain and V. V. Vazirani, APPROX '00: Proceedings of the Third International Workshop on Approximation Algorithms for Combinatorial Optimization, Spinger, New York, 2000, pp. 177-183] requires computing a minimum-cost connection scheme such that each city connects to a specified number of facilities. When each city connects to exactly one facility, FTFL becomes the classical uncapacitated facility location problem (UFL) that is well-known NP hard. The current best solution to FTFL admits an approximation ratio 1.7245 due to Byrka, Srinivasan, and Swamy applying the dependent rounding technique announced recently [Proceedings of IPCO, 2010, pp. 244-257], which improves the ratio 2.076 obtained by Swamy and Shmoys based on LP rounding [ACM Trans. Algorithms, 4 (2008), pp. 1-27]. In this paper, we study a variant of the FTFL problem, namely, fault tolerant facility allocation (FTFA), as another generalization of UFL by allowing each site to hold multiple facilities and show that we can obtain better solutions for this problem. We first give two algorithms with 1.81 and 1.61 approximation ratios in time complexity O(m R log m) and O(Rn³), respectively, where R is the maximum number of facilities required by any city, m = nfnc, and n = max{nf, nc}. Instead of applying the dual-fitting technique that reduces the dual problem's solution to fit the original problem as used in the literature [K. Jain et al., Journal of the ACM, 50 (2003), pp. 795-824; K. Jain, M. Mahdian, and A. Saberi, STOC'02: Proceedings of the 34th Annual ACM Symposium on the Theory of Computing, New York, 2002, pp. 731-740; A. Saberi et al., Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques, Springer, New York, 2001, pp. 127-137], we propose a method called inverse dual-fitting that alters the original problem to fit the dual solution and show that this method is more effective for obtaining solutions of multifactor approximation. We show that applying inverse dual-fitting and factor-revealing techniques our second algorithm is also (1.11,1.78)- and (1,2)-approximation simultaneously. These results can be further used to achieve solutions of 1.52-approximation to FTFA and 4-approximation to the fault tolerant k-facility allocation problem in which the total number of facilities is bounded by k. These are currently the best bifactor and single-factor approximation ratios for the problems concerned. [ABSTRACT FROM AUTHOR]

In the minimum-cost k-(S,T) connected digraph (abbreviated as k-(S,T) connectivity) problem we are given a positive integer k, a directed graph G = (V, E) with nonnegative costs on the edges, and two subsets S, T of V; the goal is to find a subset of edges Ê of minimum cost such that the subgraph (V, Ê) has k edge-disjoint directed paths from each vertex in S to each vertex in T. Most of our results focus on a specialized version of the problem that we call the standard version, where every edge of positive cost has its tail in S and its head in T. This version of the problem captures NP-hard problems such as the minimum-cost k-vertex connected spanning subgraph problem. We give an approximation algorithm with a guarantee of O((logk)(logn)) for the standard version of the k-(S,T) connectivity problem, where n denotes the number of vertices. For k = 1, we give a simple 2-approximation algorithm that generalizes a well-known 2-approximation algorithm for the minimum-cost strongly connected spanning subgraph problem. For k = 2, we give a 3-approximation algorithm; this matches the best approximation guarantee known for the special case of the minimum-cost 2-vertex connected spanning subgraph problem. Besides the standard version, we study another version that is intermediate between the standard version and the problem in its full generality. In the relaxed version of the (S, T) connectivity problem, each edge of positive cost has its head in T but there is no restriction on the tail. We study the relaxed version with the connectivity parameter k fixed at one and observe that this version is at least as hard to approximate as the directed Steiner tree problem. We match this by giving an algorithm that achieves an approximation guarantee of α(n) +1 for the relaxed (S, T) connectivity problem, where α(n) denotes the best approximation guarantee available for the directed Steiner tree problem. The key to the analysis is a structural result that decomposes any feasible solution into a set of so-called junction trees that are disjoint on the vertices of T. Our algorithm and analysis specialize to the case when the input digraph is acyclic on T, meaning that there exists no dicycle that contains two distinct vertices of T. In this setting, we show that the relaxed (S, T) connectivity problem is at least as hard to approximate as the set covering problem, and we prove that our algorithm achieves a matching approximation guarantee of O(log |S|). [ABSTRACT FROM AUTHOR]