Search

We show that, for planar point sets, the number of non-crossing Hamiltonian paths is polynomially bounded in the number of non-crossing paths, and the number of non-crossing Hamiltonian cycles (polygonalizations) is polynomially bounded in the number of surrounding cycles. As a consequence, we can list the non-crossing Hamiltonian paths or the polygonalizations, in time polynomial in the output size, by filtering the output of simple backtracking algorithms for non-crossing paths or surrounding cycles respectively. We do not assume that the points are in general position. To prove these results we relate the numbers of non-crossing structures to two easily-computed parameters of the point set: the minimum number of points whose removal results in a collinear set, and the number of points interior to the convex hull. These relations also lead to polynomial-time approximation algorithms for the numbers of structures of all four types, accurate to within a constant factor of the logarithm of these numbers. [ABSTRACT FROM AUTHOR]

The two-watchman route problem is that of computing a pair of closed tours in an environment so that the two tours together see the whole environment and some length measure on the two tours is minimized. Two standard measures are: the minmax measure, where we want the tours where the longest of them has smallest length, and the minsum measure, where we want the tours for which the sum of their lengths is the smallest. It is known that computing a minmax two-watchman route is NP-hard for simple rectilinear polygons and thus also for simple polygons. Also, any c-approximation algorithm for the minmax two-watchman route is automatically a 2c-approximation algorithm for the minsum two-watchman route. We exhibit two constant factor approximation algorithms for computing minmax two-watchman routes in simple polygons with approximation factors 5.969 and 11.939, having running times O (n 8) and O (n 4) respectively, where n is the number of vertices of the polygon. We also use the same techniques to obtain a 6.922-approximation for the fixed two-watchman route problem running in O (n 2) time, i.e., when two starting points of the two tours are given as input. [ABSTRACT FROM AUTHOR]

In this paper we consider the following problem: Given a Hamiltonian graph G, and a Hamiltonian cycle C of G, can we compute a second Hamiltonian cycle C ′ ≠ C of G, and if yes, how quickly? If the input graph G satisfies certain conditions (e.g. if every vertex of G is odd, or if the minimum degree is large enough), it is known that such a second Hamiltonian cycle always exists. Despite substantial efforts, no subexponential-time algorithm is known for this problem. In this paper we relax the problem of computing a second Hamiltonian cycle in two ways. First, we consider approximating the length of a second longest cycle on n-vertex graphs with minimum degree δ and maximum degree Δ . We provide a linear-time algorithm for computing a cycle C ′ ≠ C of length at least n - 4 α (n + 2 α) + 8 , where α = Δ - 2 δ - 2 . This results provides a constructive proof of a recent result by Girão, Kittipassorn, and Narayanan in the regime of Δ δ = o (n) . Our second relaxation of the problem is probabilistic. We propose a randomized algorithm which computes a second Hamiltonian cycle with high probability, given that the input graph G has a large enough minimum degree. More specifically, we prove that for every 0 < p ≤ 0.02 , if the minimum degree of G is at least 8 p log 8 n + 4 , then a second Hamiltonian cycle can be computed with probability at least 1 - 1 n 50 p 4 + 1 in p o l y (n) · 2 4 p n time. This result implies that, when the minimum degree δ is sufficiently large, we can compute with high probability a second Hamiltonian cycle faster than any known deterministic algorithm. In particular, when δ = ω (log n) , our probabilistic algorithm works in 2 o (n) time. [ABSTRACT FROM AUTHOR]

Parameterization above (or below) a guarantee is a successful concept in parameterized algorithms. The idea is that many computational problems admit "natural" guarantees bringing to algorithmic questions whether a better solution (above the guarantee) could be obtained efficiently. For example, for every boolean CNF formula on m clauses, there is an assignment that satisfies at least m/2 clauses. How difficult is it to decide whether there is an assignment satisfying more than m / 2 + k clauses? Or, if an n-vertex graph has a perfect matching, then its vertex cover is at least n/2. Is there a vertex cover of size at least n / 2 + k for some k ≥ 1 and how difficult is it to find such a vertex cover? The above guarantee paradigm has led to several exciting discoveries in the areas of parameterized algorithms and kernelization. We argue that this paradigm could bring forth fresh perspectives on well-studied problems in approximation algorithms. Our example is the longest cycle problem. One of the oldest results in extremal combinatorics is the celebrated Dirac's theorem from 1952. Dirac's theorem provides the following guarantee on the length of the longest cycle: for every 2-connected n-vertex graph G with minimum degree δ (G) ≤ n / 2 , the length of a longest cycle L is at least 2 δ (G) . Thus the "essential" part in finding the longest cycle is in approximating the "offset" k = L - 2 δ (G) . The main result of this paper is the above-guarantee approximation theorem for k. Informally, the theorem says that approximating the offset k is not harder than approximating the total length L of a cycle. In other words, for any (reasonably well-behaved) function f, a polynomial time algorithm constructing a cycle of length f(L) in an undirected graph with a cycle of length L, yields a polynomial time algorithm constructing a cycle of length 2 δ (G) + Ω (f (k)) . [ABSTRACT FROM AUTHOR]

k-center is one of the most popular clustering models. While it admits a simple 2-approximation in polynomial time in general metrics, the Euclidean version is NP-hard to approximate within a factor of 1.82, even in the plane, if one insists the dependence on k in the running time be polynomial. Without this restriction, a classic algorithm by Agarwal and Procopiuc [Algorithmica 2002] yields an O (n log k) + (1 / ϵ) O (2 d k 1 - 1 / d log k) -time (1 + ϵ) -approximation for Euclidean k-center, where d is the dimension. We show for a closely related problem, k-supplier, the double-exponential dependence on dimension is unavoidable if one hopes to have a sub-linear dependence on k in the exponent. We also derive similar algorithmic results to the ones by Agarwal and Procopiuc for both k-center and k-supplier. We use a relatively new tool, called Voronoi separator, which makes our algorithms and analyses substantially simpler. Furthermore we consider a well-studied generalization of k-center, called Non-uniform k-center (NUkC), where we allow different radii clusters. NUkC is NP-hard to approximate within any factor, even in the Euclidean case. We design a 2 O (k log k) n 2 time 3-approximation for NUkC in general metrics, and a 2 O ((k log k) / ϵ) d n time (1 + ϵ) -approximation for Euclidean NUkC. The latter time bound matches the bound for k-center. [ABSTRACT FROM AUTHOR]

Reoptimization is a setting in which we are given a good approximate solution of an optimization problem instance and a local modification that slightly changes the instance. The main goal is that of finding a good approximate solution of the modified instance. We investigate one of the most studied scenarios in reoptimization known as Steiner tree reoptimization. Steiner tree reoptimization is a collection of strongly NP -hard optimization problems that are defined on top of the classical Steiner tree problem and for which several constant-factor approximation algorithms have been designed in the last decades. In this paper we improve upon all these results by developing a novel technique that allows us to design polynomial-time approximation schemes. Remarkably, prior to this paper, no approximation algorithm better than recomputing a solution from scratch was known for the elusive scenario in which the cost of a single edge decreases. Our results are best possible since none of the problems addressed in this paper admits a fully polynomial-time approximation scheme, unless P = NP [ABSTRACT FROM AUTHOR]

Given a graph, the general problem to cover the maximum number of vertices by a collection of vertex-disjoint long paths seems to escape from the literature. A path containing at least k vertices is considered long. When k ≤ 3 , the problem is polynomial time solvable; when k is the total number of vertices, the problem reduces to the Hamiltonian path problem, which is NP-complete. For a fixed k ≥ 4 , the problem is NP-hard and the best known approximation algorithm for the weighted set packing problem implies a k-approximation algorithm. To the best of our knowledge, there is no approximation algorithm directly designed for the general problem; when k = 4 , the problem admits a 4-approximation algorithm which was presented recently. We propose the first (0.4394 k + O (1)) -approximation algorithm for the general problem and an improved 2-approximation algorithm when k = 4 . Both algorithms are based on local improvement, and their theoretical performance analyses are done via amortization and their practical performance is examined through simulation studies. [ABSTRACT FROM AUTHOR]

We address long-standing open questions raised by Williamson, Goemans, Vazirani and Mihail pertaining to the design of approximation algorithms for problems in network design via the primal-dual method (Williamson et al. in Combinatorica 15(3):435–454, 1995. https://doi.org/10.1007/BF01299747). Williamson et al. prove an approximation ratio of two for connectivity augmentation problems where the connectivity requirements can be specified by uncrossable functions. They state: "Extending our algorithm to handle non-uncrossable functions remains a challenging open problem. The key feature of uncrossable functions is that there exists an optimal dual solution which is laminar... A larger open issue is to explore further the power of the primal-dual approach for obtaining approximation algorithms for other combinatorial optimization problems." Our main result proves that the primal-dual algorithm of Williamson et al. achieves an approximation ratio of 16 for a class of functions that generalizes the notion of an uncrossable function. There exist instances that can be handled by our methods where none of the optimal dual solutions has a laminar support. We present three applications of our main result to problems in the area of network design. (1) A 16 -approximation algorithm for augmenting a family of small cuts of a graph G. The previous best approximation ratio was O (log | V (G) |) . (2) A 16 · ⌈ k / u min ⌉ -approximation algorithm for the Cap-k-ECSS problem which is as follows: Given an undirected graph G = (V , E) with edge costs c ∈ Q ≥ 0 E and edge capacities u ∈ Z ≥ 0 E , find a minimum-cost subset of the edges F ⊆ E such that the capacity of any cut in (V, F) is at least k; u min (respectively, u max ) denotes the minimum (respectively, maximum) capacity of an edge in E, and w.l.o.g. u max ≤ k . The previous best approximation ratio was min (O (log | V |) , k , 2 u max) . (3) A 20 -approximation algorithm for the model of (p, 2)-Flexible Graph Connectivity. The previous best approximation ratio was O (log | V (G) |) , where G denotes the input graph. [ABSTRACT FROM AUTHOR]

We study the approximability of the maximum size independent set (MIS) problem in bounded degree graphs. This is one of the most classic and widely studied NP-hard optimization problems. It is known for its inherent hardness of approximation. We focus on the well known minimum-degree greedy algorithm for this problem. This algorithm iteratively chooses a minimum degree vertex in the graph, adds it to the solution and removes its neighbors, until the remaining graph is empty. The approximation ratios of this algorithm have been widely studied, where it is augmented with an advice that tells the greedy algorithm which minimum degree vertex to choose if it is not unique. Our main contribution is a new mathematical theory for the design of such greedy algorithms for MIS with efficiently computable advice and for the analysis of their approximation ratios. Using this theory we obtain the ultimate approximation ratio of 5/4 for greedy algorithms on graphs with maximum degree 3, which completely solves an open problem from the paper by Halldórsson and Yoshihara (in: Staples, Eades, Katoh, Moffat (eds) Algorithms and computations—ISAAC '95, in 2026 LNCS, Springer, Berlin, Heidelberg, 1995). Our algorithm is the fastest currently known algorithm for MIS with this approximation ratio on such graphs. We also obtain a simple and short proof of the (Δ + 2) / 3 -approximation ratio of any greedy algorithms on graphs with maximum degree Δ , the result proved previously by Halldórsson and Radhakrishnan (Nord J Comput 1:475–492, 1994). We almost match this ratio by showing a lower bound of (Δ + 1) / 3 on the ratio of a greedy algorithm that can use an advice. We apply our new algorithm to the minimum vertex cover problem on graphs with maximum degree 3 to obtain a substantially faster 6/5-approximation algorithm than the one currently known. We complement our algorithmic, upper bound results with lower bound results, which show that the problem of designing good advice for greedy algorithms for MIS is computationally hard and even hard to approximate on various classes of graphs. These results significantly improve on the previously known hardness results. Moreover, these results suggest that obtaining the upper bound results on the design and analysis of the greedy advice is non-trivial. [ABSTRACT FROM AUTHOR]

Motivated by an application from geodesy, we study the connected k-center problem and the connected k-diameter problem. The former problem has been introduced by Ge et al. (ACM Trans Knowl Discov Data 2(2):1–35, 2008. https://doi.org/10.1145/1376815.1376816) to model clustering of data sets with both attribute and relationship data. These problems arise from the classical k-center and k-diameter problems by adding a side constraint. For the side constraint, we are given an undirected connectivity graphG on the input points, and a clustering is now only feasible if every cluster induces a connected subgraph in G. Usually in clustering problems one assumes that the clusters are pairwise disjoint. We study this case but additionally also the case that clusters are allowed to be non-disjoint. This can help to satisfy the connectivity constraints. Our main result is an O (log 2 k) -approximation algorithm for the disjoint connected k-center and k-diameter problem. For Euclidean spaces of constant dimension and for metrics with constant doubling dimension, the approximation factor improves to O(1). Our algorithm works by computing a non-disjoint connected clustering first and transforming it into a disjoint connected clustering. We complement these upper bounds by several upper and lower bounds for variations and special cases of the model. [ABSTRACT FROM AUTHOR]

We present a new generalization of the bin covering problem that is known to be a strongly NP-hard problem. In our generalization there is a positive constant Δ , and we are given a set of items each of which has a positive size. We would like to find a partition of the items into bins. We say that a bin is near exact covered if the total size of items packed into the bin is between 1 and 1 + Δ . Our goal is to maximize the number of near exact covered bins. If Δ = 0 or Δ > 0 is given as part of the input, our problem is shown here to have no approximation algorithm with a bounded asymptotic approximation ratio (assuming that P ≠ N P ). However, for the case where Δ > 0 is seen as a constant, we present an asymptotic fully polynomial time approximation scheme (AFPTAS) that is our main contribution. [ABSTRACT FROM AUTHOR]

We study the problem of approximating the eigenspectrum of a symmetric matrix A ∈ R n × n with bounded entries (i.e., ‖ A ‖ ∞ ≤ 1 ). We present a simple sublinear time algorithm that approximates all eigenvalues of A up to additive error ± ϵ n using those of a randomly sampled O ~ log 3 n ϵ 3 × O ~ log 3 n ϵ 3 principal submatrix. Our result can be viewed as a concentration bound on the complete eigenspectrum of a random submatrix, significantly extending known bounds on just the singular values (the magnitudes of the eigenvalues). We give improved error bounds of ± ϵ nnz (A) and ± ϵ ‖ A ‖ F when the rows of A can be sampled with probabilities proportional to their sparsities or their squared ℓ 2 norms respectively. Here nnz (A) is the number of non-zero entries in A and ‖ A ‖ F is its Frobenius norm. Even for the strictly easier problems of approximating the singular values or testing the existence of large negative eigenvalues (Bakshi, Chepurko, and Jayaram, FOCS '20), our results are the first that take advantage of non-uniform sampling to give improved error bounds. From a technical perspective, our results require several new eigenvalue concentration and perturbation bounds for matrices with bounded entries. Our non-uniform sampling bounds require a new algorithmic approach, which judiciously zeroes out entries of a randomly sampled submatrix to reduce variance, before computing the eigenvalues of that submatrix as estimates for those of A . We complement our theoretical results with numerical simulations, which demonstrate the effectiveness of our algorithms in practice. [ABSTRACT FROM AUTHOR]

In the Determinant Maximization problem, given an n × n positive semi-definite matrix A in Q n × n and an integer k, we are required to find a k × k principal submatrix of A having the maximum determinant. This problem is known to be NP-hard and further proven to be W[1]-hard with respect to k by Koutis (Inf Process Lett 100:8–13, 2006); i.e., a f (k) n O (1) -time algorithm is unlikely to exist for any computable function f. However, there is still room to explore its parameterized complexity in the restricted case, in the hope of overcoming the general-case parameterized intractability. In this study, we rule out the fixed-parameter tractability of Determinant Maximization even if an input matrix is extremely sparse or low rank, or an approximate solution is acceptable. We first prove that Determinant Maximization is NP-hard and W[1]-hard even if an input matrix is an arrowhead matrix; i.e., the underlying graph formed by nonzero entries is a star, implying that the structural sparsity is not helpful. By contrast, Determinant Maximization is known to be solvable in polynomial time on tridiagonal matrices (Al-Thani and Lee, in: LAGOS, 2021). Thereafter, we demonstrate the W[1]-hardness with respect to the rankr of an input matrix. Our result is stronger than Koutis' result in the sense that any k × k principal submatrix is singular whenever k > r . We finally give evidence that it is W[1]-hard to approximate Determinant Maximization parameterized by k within a factor of 2 - c k for some universal constant c > 0 . Our hardness result is conditional on the Parameterized Inapproximability Hypothesis posed by Lokshtanov et al. (in: SODA, 2020), which asserts that a gap version of Binary Constraint Satisfaction Problem is W[1]-hard. To complement this result, we develop an ε -additive approximation algorithm that runs in ε - r 2 · r O (r 3) · n O (1) time for the rank r of an input matrix, provided that the diagonal entries are bounded. [ABSTRACT FROM AUTHOR]

In this paper we study the classical problem of throughput maximization. In this problem we have a collection J of n jobs, each having a release time r j , deadline d j , and processing time p j . They have to be scheduled non-preemptively on m identical parallel machines. The goal is to find a schedule which maximizes the number of jobs scheduled entirely in their [ r j , d j ] window. This problem has been studied extensively (even for the case of m = 1 ). Several special cases of the problem remain open. Bar-Noy et al. (Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, May 1–4, 1999, Atlanta, Georgia, USA, pp. 622–631. ACM, 1999, https://doi.org/10.1145/301250.301420) presented an algorithm with ratio 1 - 1 / (1 + 1 / m) m for m machines, which approaches 1 - 1 / e as m increases. For m = 1 , Chuzhoy et al. (42nd Annual Symposium on Foundations of Computer Science (FOCS) 2001, 14–17 October 2001, Las Vegas, Nevada, USA, pp. 348–356. IEEE Computer Society, 2001) presented an algorithm with approximation with ratio 1 - 1 e - ε (for any ε > 0 ). Recently Im et al. (SIAM J Discrete Math 34(3):1649–1669, 2020) presented an algorithm with ratio 1 - 1 / e + ε 0 for some absolute constant ε 0 > 0 for any fixed m. They also presented an algorithm with ratio 1 - O (log m / m) - ε for general m which approaches 1 as m grows. The approximability of the problem for m = O (1) remains a major open question. Even for the case of m = 1 and c = O (1) distinct processing times the problem is open (Sgall in: Algorithms - ESA 2012 - 20th Annual European Symposium, Ljubljana, Slovenia, September 10–12, 2012. Proceedings, pp 2–11, 2012). In this paper we study the case of m = O (1) and show that if there are c distinct processing times, i.e. p j 's come from a set of size c, then there is a randomized (1 - ε) -approximation that runs in time O (n m c 7 ε - 6 log T) , where T is the largest deadline. Therefore, for constant m and constant c this yields a PTAS. Our algorithm is based on proving structural properties for a near optimum solution that allows one to use a dynamic programming with pruning. [ABSTRACT FROM AUTHOR]

In offline scheduling models, jobs are given with their exact processing times. In their online counterparts, jobs arrive in sequence together with their processing times and the scheduler makes irrevocable decisions on how to execute each of them upon its arrival. We consider a semi-online variant which has equally rich application background, called scheduling with testing, where the exact processing time of a job is revealed only after a required testing operation is finished, or otherwise the job has to be executed for a given possibly over-estimated length of time. For multiprocessor scheduling with testing to minimize the total job completion time, we present several first approximation algorithms with constant competitive ratios for various settings, including a 2 φ -competitive algorithm for the non-preemptive general testing case and a (0.0382 + 2.7925 (1 - 1 2 m)) -competitive randomized algorithm, when the number of machines m ≥ 37 or otherwise 2.7925-competitive, where φ = (1 + 5) / 2 < 1.6181 is the golden ratio and m is the number of machines, a (3.5 - 3 2 m) -competitive algorithm allowing job preemption when m ≥ 3 or otherwise 3-competitive, and a (φ + φ + 1 2 (1 - 1 m)) -competitive algorithm for the non-preemptive uniform testing case when m ≥ 5 or otherwise (φ + 1) -competitive. Our results improve three previous best approximation algorithms for the single machine scheduling with testing problems, respectively. [ABSTRACT FROM AUTHOR]

Stochastic optimization has experienced significant growth in recent decades, with the increasing prevalence of variance reduction techniques in stochastic optimization algorithms to enhance computational efficiency. In this paper, we introduce two projection-free stochastic approximation algorithms for maximizing diminishing return (DR) submodular functions over convex constraints, building upon the Stochastic Path Integrated Differential EstimatoR (SPIDER) and its variants. Firstly, we present a SPIDER Continuous Greedy (SPIDER-CG) algorithm for the monotone case that guarantees a (1 - e - 1) OPT - ε approximation after O (ε - 1) iterations and O (ε - 2) stochastic gradient computations under the mean-squared smoothness assumption. For the non-monotone case, we develop a SPIDER Frank–Wolfe (SPIDER-FW) algorithm that guarantees a 1 4 (1 - min x ∈ C ‖ x ‖ ∞) OPT - ε approximation with O (ε - 1) iterations and O (ε - 2) stochastic gradient estimates. To address the practical challenge associated with a large number of samples per iteration, we introduce a modified gradient estimator based on SPIDER, leading to a Hybrid SPIDER-FW (Hybrid SPIDER-CG) algorithm, which achieves the same approximation guarantee as SPIDER-FW (SPIDER-CG) algorithm with only O (1) samples per iteration. Numerical experiments on both simulated and real data demonstrate the efficiency of the proposed methods. [ABSTRACT FROM AUTHOR]

In this paper, we consider the problem of finding a regression in a version control system (VCS), such as git. The set of versions is modelled by a directed acyclic graph (DAG) where vertices represent versions of the software, and arcs are the changes between different versions. We assume that somewhere in the DAG, a bug was introduced, which persists in all of its subsequent versions. It is possible to query a vertex to check whether the corresponding version carries the bug. Given a DAG and a bugged vertex, the Regression Search Problem consists in finding the first vertex containing the bug in a minimum number of queries in the worst-case scenario. This problem is known to be NP-complete. We study the algorithm used in git to address this problem, known as git bisect. We prove that in a general setting, git bisect can use an exponentially larger number of queries than an optimal algorithm. We also consider the restriction where all vertices have indegree at most 2 (i.e. where merges are made between at most two branches at a time in the VCS), and prove that in this case, git bisect is a 1 log 2 (3 / 2) -approximation algorithm, and that this bound is tight. We also provide a better approximation algorithm for this case. Finally, we give an alternative proof of the NP-completeness of the Regression Search Problem, via a variation with bounded indegree. [ABSTRACT FROM AUTHOR]

In this work, we introduce a multi-vehicle (or multi-postman) extension of the classical Mixed Rural Postman Problem, which we call the Min–Max Mixed Rural Postmen Cover Problem (MRPCP). The MRPCP is defined on a mixed graph G = (V , E , A) , where V is the vertex set, E denotes the (undirected) edge set and A represents the (directed) arc set. Let F ⊆ E ( H ⊆ A ) be the set of required edges (required arcs). There is a nonnegative weight associated with each edge and arc. The objective is to determine no more than k closed walks to cover all the required edges in F and all the required arcs in H such that the weight of the maximum weight closed walk is minimized. By replacing closed walks with (open) walks in the MRPCP, we obtain the Min–Max Mixed Rural Postmen Walk Cover Problem (MRPWCP). The Min–Max Mixed Chinese Postmen Cover Problem (MCPCP) is a special case of the MRPCP where F = E and H = A . The Min–Max Stacker Crane Cover Problem (SCCP) is another special case of the MRPCP where F = ∅ and H = A For the MRPCP with the input graph satisfying the weakly symmetric condition, i.e., for each arc there exists a parallel edge whose weight is not greater than this arc, we devise a 27 4 -approximation algorithm. This algorithm achieves an approximation ratio of 33 5 for the SCCP with the weakly symmetric condition. Moreover, we obtain the first 5-approximation algorithm (4-approximation algorithm) for the MRPWCP (MCPCP) with the weakly symmetric condition. [ABSTRACT FROM AUTHOR]

In the 70 s, Berge introduced 1-extendable graphs (also called B-graphs), which are graphs where every vertex belongs to a maximum independent set. Motivated by an application in the design of wireless networks, we study the computational complexity of 1-extendability, the problem of deciding whether a graph is 1-extendable. We show that, in general, 1-extendability cannot be solved in 2 o (n) time assuming the Exponential Time Hypothesis, where n is the number of vertices of the input graph, and that it remains NP-hard in subcubic planar graphs and in unit disk graphs (which is a natural model for wireless networks). Although 1-extendability seems to be very close to the problem of finding an independent set of maximum size (a.k.a.Maximum Independent Set), we show that, interestingly, there exist 1-extendable graphs for which Maximum Independent Set is NP-hard. Finally, we investigate a parameterized version of 1-extendability. [ABSTRACT FROM AUTHOR]

In this paper, we study the following robust optimization problem. Given a set family representing feasibility and candidate objective functions, we choose a feasible set, and then an adversary chooses one objective function, knowing our choice. The goal is to find a randomized strategy (i.e., a probability distribution over the feasible sets) that maximizes the expected objective value in the worst case. This problem is fundamental in wide areas such as artificial intelligence, machine learning, game theory, and optimization. To solve the problem, we provide a general framework based on the dual linear programming problem. In the framework, we utilize the ellipsoid algorithm with the approximate separation algorithm. We prove that there exists an α -approximation algorithm for our robust optimization problem if there exists an α -approximation algorithm for finding a (deterministic) feasible set that maximizes a nonnegative linear combination of the candidate objective functions. Using our result, we provide approximation algorithms for the max–min fair randomized allocation problem and the maximum cardinality robustness problem with a knapsack constraint. [ABSTRACT FROM AUTHOR]

In the general max–min fair allocation problem, there are m players and n indivisible resources, each player has his/her own utilities for the resources, and the goal is to find an assignment that maximizes the minimum total utility of resources assigned to a player. The problem finds many natural applications such as bandwidth distribution in telecom networks, processor allocation in computational grids, and even public-sector decision making. We introduce an over-estimation strategy to design approximation algorithms for this problem. When all utilities are positive, we obtain an approximation ratio of c 1 - ϵ , where c is the maximum ratio of the largest utility to the smallest utility of any resource. When some utilities are zero, we obtain an approximation ratio of (1 + 3 c ^ + O (δ c ^ 2)) , where c ^ is the maximum ratio of the largest utility to the smallest positive utility of any resource. [ABSTRACT FROM AUTHOR]

We consider the robust version of the classic k-center clustering problem, where we wish to remove up to z points (outliers), so as to be able to cluster the remaining points in k clusters with minimum maximum radius. We study such a problem under the fully dynamic adversarial model, where points can be inserted or deleted arbitrarily. In this setting, the main goal is to design algorithms that maintain a high quality solution at any point in time, while requiring a "small" amortized cost, i.e. a "small" number of operations per insertion or deletion, on average. In our work, we provide the first constant bi-criteria approximation algorithm for such a problem with its amortized cost being independent of both z and the size of the current input. We also complement our positive result with a lower bound showing that any constant (non bi-criteria) approximation algorithm has amortized cost at least linear in z. Finally, we conduct an in-depth experimental analysis of our algorithm on Twitter, Flickr, and Air-Quality datasets showing the effectiveness of our approach. [ABSTRACT FROM AUTHOR]

We prove that Simulated Annealing with an appropriate cooling schedule computes arbitrarily tight constant-factor approximations to the minimum spanning tree problem in polynomial time. This result was conjectured by Wegener (Automata, Languages and Programming, ICALP, Berlin, 2005). More precisely, denoting by n , m , w max , and w min the number of vertices and edges as well as the maximum and minimum edge weight of the MST instance, we prove that simulated annealing with initial temperature T 0 ≥ w max and multiplicative cooling schedule with factor 1 - 1 / ℓ , where ℓ = ω (m n ln (m)) , with probability at least 1 - 1 / m computes in time O (ℓ (ln ln (ℓ) + ln (T 0 / w min))) a spanning tree with weight at most 1 + κ times the optimum weight, where 1 + κ = (1 + o (1)) ln (ℓ m) ln (ℓ) - ln (m n ln (m)) . Consequently, for any ϵ > 0 , we can choose ℓ in such a way that a (1 + ϵ) -approximation is found in time O ((m n ln (n)) 1 + 1 / ϵ + o (1) (ln ln n + ln (T 0 / w min))) with probability at least 1 - 1 / m . In the special case of so-called (1 + ϵ) -separated weights, this algorithm computes an optimal solution (again in time O ((m n ln (n)) 1 + 1 / ϵ + o (1) (ln ln n + ln (T 0 / w min))) ), which is a significant speed-up over Wegener's runtime guarantee of O (m 8 + 8 / ϵ) . Our tighter upper bound also admits the result that in some situations a hybridization of simulated annealing and the (1 + 1) EA can lead to stronger runtime guarantees than either algorithm alone. [ABSTRACT FROM AUTHOR]

Simple heuristics for (combinatorial) optimization problems often show a remarkable performance in practice. Worst-case analysis often falls short of explaining this performance. Because of this, "beyond worst-case analysis" of algorithms has recently gained a lot of attention, including probabilistic analysis of algorithms. The instances of many (combinatorial) optimization problems are essentially a discrete metric space. Probabilistic analysis for such metric optimization problems has nevertheless mostly been conducted on instances drawn from Euclidean space, which provides a structure that is usually heavily exploited in the analysis. However, most instances from practice are not Euclidean. Little work has been done on metric instances drawn from other, more realistic, distributions. Some initial results have been obtained in recent years, where random shortest path metrics generated from dense graphs (either complete graphs or Erdős–Rényi random graphs) have been used so far. In this paper we extend these findings to sparse graphs, with a focus on sparse graphs with 'fast growing cut sizes', i.e. graphs for which | δ (U) | = Ω (| U | ε) for some constant ε ∈ (0 , 1) for all subsets U of the vertices, where δ (U) is the set of edges connecting U to the remaining vertices. A random shortest path metric is constructed by drawing independent random edge weights for each edge in the graph and setting the distance between every pair of vertices to the length of a shortest path between them with respect to the drawn weights. For such instances generated from a sparse graph with fast growing cut sizes, we prove that the greedy heuristic for the minimum distance maximum matching problem, and the nearest neighbor and insertion heuristics for the traveling salesman problem all achieve a constant expected approximation ratio. Additionally, for instances generated from an arbitrary sparse graph, we show that the 2-opt heuristic for the traveling salesman problem also achieves a constant expected approximation ratio. [ABSTRACT FROM AUTHOR]

We study the Non-preemptive Peak Demand Minimization (NPDM) problem, where we are given a set of jobs, specified by their processing times and energy requirements. The goal is to schedule all jobs within a fixed time period such that the peak load (the maximum total energy requirement at any time) is minimized. This problem has recently received significant attention due to its relevance in smart-grids. Theoretically, the problem is related to the classical strip packing problem (SP). In SP, a given set of axis-aligned rectangles must be packed into a fixed-width strip, such that the height of the strip is minimized. NPDM can be modeled as strip packing with slicing and stacking constraint: each rectangle may be cut vertically into multiple slices and the slices may be packed into the strip as individual pieces. The stacking constraint forbids solutions where two slices of the same rectangle are intersected by the same vertical line. Non-preemption enforces the slices to be placed in contiguous horizontal locations (but may be placed at different vertical locations). We obtain a (5 / 3 + ε) -approximation algorithm for the problem. We also provide an asymptotic efficient polynomial-time approximation scheme (AEPTAS) which generates a schedule for almost all jobs with energy consumption (1 + ε) OPT . The remaining jobs fit into a thin container of height 1. This AEPTAS is used as a subroutine to acquire the (5 / 3 + ε) -approximation algorithm. The previous best result for NPDM was a 2.7-approximation based on FFDH (Ranjan et al., in: 2015 IEEE symposium on computers and communication (ISCC), pp 758–763, IEEE, 2015). One of our key ideas is providing several new lower bounds on the optimal solution of a geometric packing, which could be useful in other related problems. These lower bounds help us to obtain approximative solutions based on Steinberg's algorithm in many cases. In addition, we show how to split schedules generated by the AEPTAS into few segments and to rearrange the corresponding jobs to insert the thin container mentioned above, such that it does not exceed the bound of (5 / 3 + ε) OPT . [ABSTRACT FROM AUTHOR]

We present deterministic algorithms for maintaining a (3 / 2 + ϵ) and (2 + ϵ) -approximate maximum matching in a fully dynamic graph with worst-case update times O ^ (n) and O ~ (1) respectively. The fastest known deterministic worst-case update time algorithms for achieving approximation ratio (2 - δ) (for any δ > 0 ) and (2 + ϵ) were both shown by Roghani et al. (Beating the folklore algorithm for dynamic matching, 2021) with update times O (n 3 / 4) and O ϵ (n) respectively. We close the gap between worst-case and amortized algorithms for the two approximation ratios as the best deterministic amortized update times for the problem are O ϵ (n) and O ~ (1) which were shown in Bernstein and Stein (in: Proceedings of the twenty-seventh annual ACM-SIAM symposium on discrete algorithms, 2016) and Bhattacharya and Kiss (in: 48th international colloquium on automata, languages, and programming, ICALP 2021, 12–16 July, Glasgow, 2021) respectively. The algorithm achieving (3 / 2 + ϵ) approximation builds on the EDCS concept introduced by the influential paper of Bernstein and Stein (in: International colloquium on automata, languages, and programming, Springer, Berlin, 2015). Say that H is a (α , δ) -approximate matching sparsifier if at all times H satisfies that μ (H) · α + δ · n ≥ μ (G) (define (α , δ) -approximation similarly for matchings). We show how to maintain a locally damaged version of the EDCS which is a (3 / 2 + ϵ , δ) -approximate matching sparsifier. We further show how to reduce the maintenance of an α -approximate maximum matching to the maintenance of an (α , δ) -approximate maximum matching building based on an observation of Assadi et al. (in: Proceedings of the twenty-seventh annual (ACM-SIAM) symposium on discrete algorithms, (SODA) 2016, Arlington, VA, USA, January 10–12, 2016). Our reduction requires an update time blow-up of O ^ (1) or O ~ (1) and is deterministic or randomized against an adaptive adversary respectively. To achieve (2 + ϵ) -approximation we improve on the update time guarantee of an algorithm of Bhattacharya and Kiss (in: 48th International colloquium on automata, languages, and programming, ICALP 2021, 12–16 July, Glasgow, 2021). In order to achieve both results we explicitly state a method implicitly used in Nanongkai and Saranurak (in: Proceedings of the twenty-seventh annual ACM symposium on theory of computing, 2017) and Bernstein et al. (Fully-dynamic graph sparsifiers against an adaptive adversary, 2020) which allows to transform dynamic algorithms capable of processing the input in batches to a dynamic algorithms with worst-case update time. [ABSTRACT FROM AUTHOR]

For a graph G = (V , E) , a collection P of vertex-disjoint (simple) paths is called a path cover of G if every vertex v ∈ V is contained in exactly one path of P . The Path Cover problem (PC for short) is to find a minimum cardinality path cover of G. In this paper, we introduce generalizations of PC, where each path is associated with a weight (cost or profit). Our problem, Minimum (Maximum) Weighted Path Cover [MinPC (MaxPC)], is defined as follows: Let U = { 0 , 1 , ⋯ , n - 1 } . Given a graph G = (V , E) and a weight function f : U → R ∪ { + ∞ , - ∞ } that defines a weight for each path based on its length, the objective of MinPC (MaxPC) is to find a path cover P of G such that the total weight of the paths in P is minimized (maximized). Let L be a subset of U, and P L be the set of paths such that each path is of length ℓ ∈ L . We consider Min P L PC with binary cost, i.e., the cost function is f (ℓ) = 1 if ℓ ∈ L ; otherwise, f (ℓ) = 0 . We also consider Max P L PC with f (ℓ) = ℓ + 1 , if ℓ ∈ L ; otherwise, f (ℓ) = 0 . Many well-known graph theoretic problems such as the Hamiltonian Path and the Maximum Matching problems can be modeled using Min P L PC and Max P L PC. In this paper, we first show that deciding whether Min P { 0 , 1 , 2 } PC has a 0-weight solution is NP-complete for planar bipartite graphs of maximum degree three, and consequently, (i) for any constant σ ≥ 1 , there is no polynomial-time approximation algorithm with approximation ratio σ for Min P { 0 , 1 , 2 } PC unless P = NP, and (ii) Max P { 3 , ⋯ , n - 1 } PC is NP-hard for the same graph class. Next, we present a polynomial-time algorithm for Min P { 0 , 1 , ⋯ , k } PC on graphs with bounded treewidth for a fixed k. Lastly, we present a 4-approximation algorithm for Max P { 3 , ⋯ , n - 1 } PC, which becomes a 2.5-approximation algorithm for subcubic graphs. [ABSTRACT FROM AUTHOR]

In the Strip Packing problem, we are given a vertical half-strip [ 0 , W ] × [ 0 , + ∞) and a collection of open rectangles of width at most W. Our goal is to find an axis-aligned (non-overlapping) packing of such rectangles into the strip such that the maximum height OPT spanned by the packing is as small as possible. It is NP-hard to approximate this problem within a factor (3 / 2 - ε) for any constant ε > 0 by a simple reduction from the Partition problem, while the current best approximation factor for it is (5 / 3 + ε) . It seems plausible that Strip Packing admits a (3 / 2 + ε) -approximation. We make progress in that direction by achieving such tight approximation guarantees for a special family of instances, which we call skewed instances. As standard in the area, for a given constant parameter δ > 0 , we call large the rectangles with width at least δ W and height at least δ O P T , and skewed the remaining rectangles. If all the rectangles in the input are large, then one can easily compute the optimal packing in polynomial time (since the input can contain only a constant number of rectangles). We consider the complementary case where all the rectangles are skewed. This second case retains a large part of the complexity of the original problem; in particular, the skewed case is still NP-hard to approximate within a factor (3 / 2 - ε) , and we provide an (almost) tight (3 / 2 + ε) -approximation algorithm. [ABSTRACT FROM AUTHOR]

We study algorithmic Bayesian persuasion problems in which the principal (a.k.a. the sender) has to persuade multiple agents (a.k.a. receivers) by using public communication channels. Specifically, our model follows the multi-receiver model with no inter-agent externalities introduced by Arieli and Babichenko (J Econ Theory 182:185–217, 2019). It is known that the problem of computing a sender-optimal public persuasive signaling scheme is not approximable even in simple settings. Therefore, prior works usually focus on determining restricted classes of the problem for which efficient approximation is possible. Typically, positive results in this space amounts to finding bi-criteria approximation algorithms yielding an almost optimal and almost persuasive solution in polynomial time. In this paper, we take a different perspective and study the persuasion problem in the general setting where the space of the states of nature, the action space of the receivers, and the utility function of the sender can be arbitrary. We fully characterize the computational complexity of computing a bi-criteria approximation of an optimal public signaling scheme in such settings. In particular, we show that, assuming the Exponential Time Hypothesis, solving this problem requires at least a quasi-polynomial number of steps even in instances with simple utility functions and binary action spaces such as an election with the k-voting rule. In doing so, we prove that a relaxed version of the Maximum Feasible Subsystem of Linear Inequalities problem requires at least quasi-polynomial time to be solved. Finally, we close the gap by providing a quasi-polynomial time bi-criteria approximation algorithm for arbitrary public persuasion problems that, under mild assumptions, yields a QPTAS. [ABSTRACT FROM AUTHOR]

In Two-dimensional Bin Packing (2BP), we are given n rectangles as input and our goal is to find an axis-aligned nonoverlapping packing of these rectangles into the minimum number of unit square bins. 2BP admits no APTAS and the current best approximation ratio is 1.406 by Bansal and Khan (ACM-SIAM symposium on discrete algorithms (SODA), pp 13–25, 2014. https://doi.org/10.1137/1.9781611973402.2). A well-studied variant of 2BP is Guillotine Two-dimensional Bin Packing (G2BP), where rectangles must be packed in such a way that every rectangle in the packing can be obtained by applying a sequence of end-to-end axis-parallel cuts, also called guillotine cuts. Bansal et al. (Symposium on foundations of computer science (FOCS). IEEE, pp 657–666, 2005. https://doi.org/10.1109/SFCS.2005.10) gave an APTAS for G2BP. Let λ be the smallest constant such that for every set I of items, the number of bins in the optimal solution to G2BP for I is upper bounded by λ opt (I) + c , where opt (I) is the number of bins in the optimal solution to 2BP for I and c is a constant. It is known that 4 / 3 ≤ λ ≤ 1.692 . Bansal and Khan (2014) conjectured that λ = 4 / 3 . The conjecture, if true, will imply a (4 / 3 + ε) -approximation algorithm for 2BP. Given a small constant δ > 0 , a rectangle is called large if both its height and width are at least δ , else it is called skewed. We make progress towards the conjecture by showing that λ = 4 / 3 when all input rectangles are skewed. We also give an APTAS for 2BP for skewed items, though general 2BP does not admit an APTAS. [ABSTRACT FROM AUTHOR]

In the Metric Capacitated Covering (MCC) problem, given a set of balls B in a metric space P with metric d and a capacity parameter U, the goal is to find a minimum sized subset B ′ ⊆ B and an assignment of the points in P to the balls in B ′ such that each point is assigned to a ball that contains it and each ball is assigned with at most U points. MCC achieves an O (log | P |) -approximation using a greedy algorithm. On the other hand, it is hard to approximate within a factor of o (log | P |) even with β < 3 factor expansion of the balls. Bandyapadhyay et al. [Discrete and Computational Geometry 2019] showed that one can obtain an O(1)-approximation for the problem with 6.47 factor expansion of the balls. An open question left by their work is to reduce the gap between the lower bound 3 and the upper bound 6.47. In this current work, we show that it is possible to obtain an O(1)-approximation with only 4.24 factor expansion of the balls. Moreover, we show a similar upper bound of 5 for a more generalized version of MCC for which the best previously known bound was 9. We also study a closely related problem where instead of the upper bound, one needs to satisfy a lower bound on the number of points assigned to each ball in the solution. For this problem, we give an exact algorithm with only 5.83 factor expansion of the balls. All of our algorithms are based on LP rounding schemes that heavily exploit structure of fractional optimal solution. [ABSTRACT FROM AUTHOR]

We study geometric variations of the discriminating code problem. In the discrete version of the problem, a finite set of points P and a finite set of objects S are given in R d . The objective is to choose a subset S ∗ ⊆ S of minimum cardinality such that for each point p i ∈ P , the subset S i ∗ ⊆ S ∗ covering p i satisfies S i ∗ ≠ ∅ , and each pair p i , p j ∈ P , i ≠ j , we have S i ∗ ≠ S j ∗ . In the continuous version of the problem, the solution set S ∗ can be chosen freely among a (potentially infinite) class of allowed geometric objects. In the 1-dimensional case ( d = 1 ), the points in P are placed on a horizontal line L, and the objects in S are finite-length line segments aligned with L (called intervals). We show that the discrete version of this problem is NP-complete. This is somewhat surprising as the continuous version is known to be polynomial-time solvable. This is also in contrast with most geometric covering problems, which are usually polynomial-time solvable in one dimension. Still for the 1-dimensional discrete version, we design a polynomial-time 2-approximation algorithm. We also design a PTAS for both discrete and continuous versions in one dimension, for the restriction where the intervals are all required to have the same length. We then study the 2-dimensional case ( d = 2 ) for axis-parallel unit square objects. We show that both continuous and discrete versions are NP-complete, and design polynomial-time approximation algorithms that produce (16 · O P T + 1) -approximate and (64 · O P T + 1) -approximate solutions respectively, using rounding of suitably defined integer linear programming problems. Finally, we apply our techniques to a related variant of the discrete problem, where instead of points and geometric objects we just have a set S of objects. The goal is to select a small subset S ∗ of objects so that all objects of S are discriminated by their intersection with the objects of S ∗ . This problem can be viewed as a graph problem by stating it in terms of the vertices of the geometric intersection graph of S. Under this graph-theoretical form, it is known as the identifying code problem. We show that the identifying code problem for axis-parallel unit square intersection graphs (in d = 2 ) can be solved in the same manner as for the discrete version of the discriminating code problem for unit square objects described above, and all our positive approximation results still hold in this setting. [ABSTRACT FROM AUTHOR]

Facility location is a prominent optimization problem that has inspired a large quantity of both theoretical and practical studies in combinatorial optimization. Although the problem has been investigated under various settings reflecting typical structures within the optimization problems of practical interest, little is known on how the problem behaves in conjunction with parity constraints. This shortfall of understanding was rather discouraging when we consider the central role of parity in the field of combinatorics. In this paper, we present the first constant-factor approximation algorithm for the facility location problem with parity constraints. We are given as the input a metric on a set of facilities and clients, the opening cost of each facility, and the parity requirement– odd , even , or unconstrained –of every facility in this problem. The objective is to open a subset of facilities and assign every client to an open facility so as to minimize the sum of the total opening costs and the assignment distances, but subject to the condition that the number of clients assigned to each open facility must have the same parity as its requirement. Although the unconstrained facility location problem as a relaxation for this parity-constrained generalization has unbounded gap, we demonstrate that it yields a structured solution whose parity violation can be corrected at small cost. This correction is prescribed by a T-join on an auxiliary graph constructed by the algorithm. This auxiliary graph does not satisfy the triangle inequality, but we show that a carefully chosen set of shortcutting operations leads to a cheap and sparseT-join. Finally, we bound the correction cost by exhibiting a combinatorial multi-step construction of an upper bound. We also consider the parity-constrained k-center problem, the bottleneck optimization variant of parity-constrained facility location. We present the first constant-factor approximation algorithm also for this problem. [ABSTRACT FROM AUTHOR]

Ensuring fairness in computational problems has emerged as a key topic during recent years, buoyed by considerations for equitable resource distributions and social justice. It is possible to incorporate fairness in computational problems from several perspectives, such as using optimization, game-theoretic or machine learning frameworks. In this paper we address the problem of incorporation of fairness from a combinatorial optimization perspective. We formulate a combinatorial optimization framework, suitable for analysis by researchers in approximation algorithms and related areas, that incorporates fairness in maximum coverage problems as an interplay between two conflicting objectives. Fairness is imposed in coverage by using coloring constraints that minimizes the discrepancies between number of elements of different colors covered by selected sets; this is in contrast to the usual discrepancy minimization problems studied extensively in the literature where (usually two) colors are not given a priori but need to be selected to minimize the maximum color discrepancy of each individual set. Our main results are a set of randomized and deterministic approximation algorithms that attempts to simultaneously approximate both fairness and coverage in this framework. [ABSTRACT FROM AUTHOR]

We consider the problem of maximizing a non-negative monotone submodular function subject to a knapsack constraint, which is also known as the Budgeted Submodular Maximization (BSM) problem. Sviridenko (Operat Res Lett 32:41–43, 2004) showed that by guessing 3 appropriate elements of an optimal solution, and then executing a greedy algorithm, one can obtain the optimal approximation ratio of α = 1 - 1 / e ≈ 0.632 for BSM. However, the need to guess (by enumeration) 3 elements makes the algorithm of Sviridenko (Operat Res Lett 32:41–43, 2004) impractical as it leads to a time complexity of roughly O (n 5) (this time complexity can be slightly improved using the thresholding technique of Badanidiyuru & Vondrák (in: SODA, 1497–1514, 2014) but only to roughly O (n 4) ). Our main results in this paper show that fewer guesses suffice. Specifically, by making only 2 guesses (and using the thresholding technique of Badanidiyuru & Vondrák (in: SODA, 1497–1514, 2014), we get the same optimal approximation ratio of α with an improved time complexity of roughly O (n 3) . Furthermore, by making only a single guess, we get an almost as good approximation ratio of 0.6174 > 0.9767 α in roughly O (n 2) time. Prior to our work, the only approximation algorithms that were known to obtain an approximation ratio close to α for BSM were the algorithm of Sviridenko (Operat Res Lett 32:41–43, 2004) and an algorithm of Ene & Nguyen (in: ICALP, 53:1–53:12, 2019) that achieves (α - ε) -approximation. However, the algorithm of Ene & Nguyen (in: ICALP, 53:1–53:12, 2019) requires (1 / ε) O (1 / ε 4) n log 2 n time, and hence, is of theoretical interest only since (1 / ε) O (1 / ε 4) is huge even for moderate values of ε . In contrast, all the algorithms we analyze are simple and parallelizable, which makes them good candidates for practical use. Recently, Tang et al. (in: Proc ACM Meas Anal Comput Syst, 5(1): 08:1–08:22, 2021) studied a simple greedy algorithm that already has a long research history, and proved that it admits an approximation ratio of at least 0.405 (without any guesses). The last part of this paper improves over the result of Tang et al. (in: Proc ACM Meas Anal Comput Syst, 5(1): 08:1–08:22, 2021) and shows that the approximation ratio of this algorithm is within the range [0.427, 0.462]. [ABSTRACT FROM AUTHOR]

We study the problem of how to split many point sets in R d into smaller parts using a few (shared) splitting hyperplanes. This problem is related to the classical Ham-Sandwich Theorem. We provide a logarithmic approximation to the optimal solution using the greedy algorithm for submodular optimization. [ABSTRACT FROM AUTHOR]

We study the Independent Set problem in H-free graphs, i.e., graphs excluding some fixed graph H as an induced subgraph. We prove several inapproximability results both for polynomial-time and parameterized algorithms. Halldórsson [SODA 1995] showed that for every δ > 0 the Independent Set problem has a polynomial-time (d - 1 2 + δ) -approximation algorithm in K 1 , d -free graphs. We extend this result by showing that K a , b -free graphs admit a polynomial-time O (α (G) 1 - 1 / a) -approximation, where α (G) is the size of a maximum independent set in G. Furthermore, we complement the result of Halldórsson by showing that for some γ = Θ (d / log d) , there is no polynomial-time γ -approximation algorithm for these graphs, unless NP = ZPP. Bonnet et al. [Algorithmica 2020] showed that Independent Set parameterized by the size k of the independent set is W[1]-hard on graphs which do not contain (1) a cycle of constant length at least 4, (2) the star K 1 , 4 , and (3) any tree with two vertices of degree at least 3 at constant distance. We strengthen this result by proving three inapproximability results under different complexity assumptions for almost the same class of graphs (we weaken conditions (1) and (2) that G does not contain a cycle of constant length at least 5 or K 1 , 5 ). First, under the ETH, there is no f (k) · n o (k / log k) algorithm for any computable function f. Then, under the deterministic Gap-ETH, there is a constant δ > 0 such that no δ -approximation can be computed in f (k) · n O (1) time. Also, under the stronger randomized Gap-ETH there is no such approximation algorithm with runtime f (k) · n o (k) . Finally, we consider the parameterization by the excluded graph H, and show that under the ETH, Independent Set has no n o (α (H)) algorithm in H-free graphs. Also, we prove that there is no d / k o (1) -approximation algorithm for K 1 , d -free graphs with runtime f (d , k) · n O (1) , under the deterministic Gap-ETH. [ABSTRACT FROM AUTHOR]

We investigate offline and online algorithms for Round - UFPP , the problem of minimizing the number of rounds required to schedule a set of unsplittable flows of non-uniform size on a given path with heterogeneous edge capacities. Round - UFPP is known to be NP-hard and there are constant-factor approximation algorithms under the no bottleneck assumption (NBA), which stipulates that maximum size of any flow is at most the minimum global edge capacity. In this work, we present improved online and offline algorithms for Round - UFPP without the NBA. We first study offline Round - UFPP for a restricted class of instances, called α -small, where the size of each flow is at most α times the capacity of its bottleneck edge, and present an O (log (1 / (1 - α))) -approximation algorithm. Next, our main result is an online O (log log c max) -competitive algorithm for Round - UFPP where c max is the largest edge capacity, improving upon the previous best bound of O (log c max) due to Epstein et al. (SIAM J Discrete Math 23(2):822–841, 2009). These new results lead to an offline O (min (log n , log m , log log c max)) -approximation algorithm and an online O (min (log m , log log c max)) -competitive algorithm for Round - UFPP , where n is the number of flows and m is the number of edges. [ABSTRACT FROM AUTHOR]

Diameter—the task of computing the length of a longest shortest path—is a fundamental graph problem. Assuming the Strong Exponential Time Hypothesis, there is no O (n 1.99) -time algorithm even in sparse graphs (Roditty L, Williams, VV in Fast approximation algorithms for the diameter and radius of sparse graphs. In: Proceedings of the 45th Symposium on Theory of Computing Conference (STOC '13), pp 515–524. ACM, 2013). To circumvent this lower bound, we investigate which parameters allow for running times of the form f (k) (n + m) where k is the respective parameter and f is a computable function. To this end, we systematically explore a hierarchy of structural graph parameters. [ABSTRACT FROM AUTHOR]

These bounds already improve previous results for HT ht and HT ht . In I Exponential-time quantum algorithms for graph coloring problems i , the authors present an exponential-space quantum algorithm computing the chromatic number of an I n i -vertex graph with running time HT ht using quantum random access memory (QRAM). The authors also present polynomial-space quantum algorithms with running time HT ht for the I k i -coloring problem, for HT ht , without using the QRAM, as well as HT ht -time classical algorithms that can be improved quadratically by Grover's search to obtain polynomial-space quantum algorithms. [Extracted from the article]

The main contribution of this paper is the first constant factor approximation algorithm for red-blue set cover problem with unit disks. To achieve this, we first give a polynomial time algorithm for line-separable red-blue set cover problem with unit disks. We next obtain a factor 2 approximation algorithm for strip-separable red-blue set cover problem with unit disks. Finally, we obtain a constant factor approximation algorithm for red-blue set cover problem with unit disks by combining our algorithm for the strip-separable problem with the results of Ambühl et al. [1]. Our methods involve a novel decomposition of the optimal solution to line-separable problem into blocks with special structure and extensions of the sweep-line technique of Erlebach and van Leeuwen [9]. [ABSTRACT FROM AUTHOR]

We give better approximation ratios for two Steiner Tree variants by combining known algorithms: the optimum 3 -decomposition and iterative randomized rounding. The first problem is Steiner Tree with minimum number of Steiner points and bounded edge length problem ( S M T - M S P ). The input consists of a set of terminals R in the Euclidean space R 2 . A feasible solution is a Steiner tree τ spanning R with Steiner points S such that every edge in τ has length at most 1 . The objective is to minimize S . Previously, the best approximation ratio for S M T - M S P was 1 + ln (4) + ϵ ≈ 2.386 . We present a polynomial time algorithm with ratio 2.277 . The second problem is Steiner Tree in quasi-bipartite graphs. It is a Steiner Tree problem on graph G = (V , E , c) with terminal set R when the edge set E does not include any edge between two vertices in V \ R . The best-known approximation ratio for this problem is 73 60 , We improve this ratio to 298 245 . [ABSTRACT FROM AUTHOR]

We consider robust discrete minimization problems where uncertainty is defined by a convex set in the objective. Assuming the existence of an integrality gap verifier with a bounded approximation guarantee for the LP relaxation of the non-robust version of the problem, we derive approximation algorithms for the robust version under different types of uncertainty, including polyhedral and ellipsoidal uncertainty. [ABSTRACT FROM AUTHOR]

We consider the k -Prize-Collecting Steiner Tree Problem. An instance is composed of an integer k and a graph G with costs on edges and penalties on vertices. The objective is to find a tree spanning at least k vertices which minimizes the cost of the edges in the tree plus the penalties of vertices not in the tree. This is one of the most fundamental network design problems and is a common generalization of the Prize-Collecting Steiner Tree Problem and the k -Minimum Spanning Tree Problem. Our main result is a 2-approximation algorithm, which improves on the currently best known approximation factor of 3.96 and has a faster running time. The algorithm builds on a modification of the primal-dual framework of Goemans and Williamson, and reveals interesting properties that can be applied to other similar problems. [ABSTRACT FROM AUTHOR]

We study algorithms for the sliding-window model, an important variant of the data-stream model, in which the goal is to compute some function of a fixed-length suffix of the stream. We extend the smooth-histogram framework of Braverman and Ostrovsky (FOCS 2007) to almost-smooth functions, which includes all subadditive functions. Specifically, we show that if a subadditive function can be 1 + ε -approximated in the insertion-only streaming model, then it can be 2 + ε -approximated also in the sliding-window model with space complexity larger by factor O ε - 1 log w , where w is the window size. We demonstrate how our framework yields new approximation algorithms with relatively little effort for a variety of problems that do not admit the smooth-histogram technique. For example, in the frequency-vector model, a symmetric norm is subadditive and thus we obtain a sliding-window 2 + ε -approximation algorithm for it. Another example is for streaming matrices, where we derive a new sliding-window 2 + ε -approximation algorithm for Schatten 4-norm. We then consider graph streams and show that many graph problems are subadditive, including maximum submodular matching, minimum vertex-cover, and maximum k-cover, thereby deriving sliding-window O 1 -approximation algorithms for them almost for free (using known insertion-only algorithms). Finally, we design for every d ∈ 1 , 2 an artificial function, based on the maximum-matching size, whose almost-smoothness parameter is exactly d. [ABSTRACT FROM AUTHOR]

Consider the following Stochastic Score Classification problem. A doctor is assessing a patient's risk of developing a disease and can perform n different binary tests on the patient. The probability that test i is positive is p i and the outcomes of the n tests are independent. A patient's score is the total number of positive tests. Possible scores thus range between 0 and n. This range is divided into subranges, corresponding to risk classes (e.g., LOW, MEDIUM, or HIGH risk). Each test has an associated cost. To reduce testing cost, instead of performing all tests and determining an exact score, the doctor can perform tests sequentially and stop testing when it is possible to determine the patient's risk class. The problem is to determine the order in which the doctor should perform the tests, so as to minimize expected testing cost. We address the unit-cost case of the Stochastic Score Classification problem, and provide polynomial-time approximation algorithms for adaptive and non-adaptive versions of the problem. We also pose a number of open questions. [ABSTRACT FROM AUTHOR]

We introduce and study ℓ p -norm-multiway-cut: the input here is an undirected graph with non-negative edge weights along with k terminals and the goal is to find a partition of the vertex set into k parts each containing exactly one terminal so as to minimize the ℓ p -norm of the cut values of the parts. This is a unified generalization of min-sum multiway cut (when p = 1 ) and min–max multiway cut (when p = ∞ ), both of which are well-studied classic problems in the graph partitioning literature. We show that ℓ p -norm-multiway-cut is NP-hard for constant number of terminals and is NP-hard in planar graphs. On the algorithmic side, we design an O (log 1.5 n log 0.5 k) -approximation for all p ≥ 1 . We also show an integrality gap of Ω (k 1 - 1 / p) for a natural convex program and an O (k 1 - 1 / p - ϵ) -inapproximability for any constant ϵ > 0 assuming the small set expansion hypothesis. [ABSTRACT FROM AUTHOR]

Edit distance is a measurement of similarity between two sequences such as strings, point sequences, or polygonal curves. Many matching problems from a variety of areas, such as signal analysis, bioinformatics, etc., need to be solved in a geometric space. Therefore, the geometric edit distance (GED) has been studied. In this paper, we describe the first strictly sublinear approximate near-linear time algorithm for computing the GED of two point sequences in constant dimensional Euclidean space. Specifically, we present a randomized O (n log 2 n) time O (n) -approximation algorithm. Then, we generalize our result to give a randomized α -approximation algorithm for any α ∈ [ log n , n / log n ] , running in time O (n 2 / α 2 log n) . Both algorithms are Monte Carlo and return approximately optimal solutions with high probability. [ABSTRACT FROM AUTHOR]

Resource Minimization Fire Containment (RMFC) is a natural model for optimal inhibition of harmful spreading phenomena on a graph. In the RMFC problem on trees, we are given an undirected tree G, and a vertex r where the fire starts at, called root. At each time step, the firefighters can protect up to B vertices of the graph while the fire spreads from burning vertices to all their neighbors that have not been protected so far. The task is to find the smallest B that allows for saving all the leaves of the tree. The problem is hard to approximate up to any factor better than 2 even on trees unless P = NP (King and MacGillivray in Discret Math 310(3):614–621, 2010). Chalermsook and Chuzhoy (In: Proceedings of the 21st annual ACM-SIAM symposium on discrete algorithms, SODA 2010, Austin, Texas, USA, 17–19 Jan 2010, SIAM, pp 1334–1349, 2010) presented a Linear Programming (LP) based O (log ∗ n) approximation for RMFC on trees that matches the integrality gap of the natural Linear Programming relaxation. This was recently improved by Adjiashvili et al. (ACM Trans Algorithms 15(2):20:1–20:33, 2019) to a 12-approximation through a combination of LP rounding along with several new techniques. In this paper we present an asymptotic QPTAS for RMFC on trees. More specifically, let ϵ > 0 , and I be an instance of RMFC where the optimum number of firefighters to save all the leaves is O P T (I) . We present an algorithm which uses at most ⌈ (1 + ϵ) O P T (I) ⌉ many firefighters at each time step and runs in time n O (log log n / ϵ) . This suggests that the existence of an asymptotic PTAS is plausible especially since the exponent is O (log log n) , not O (log n) . Our result combines a more refined height reduction lemma than the one in Adjiashvili et al. (2019) with LP rounding and dynamic programming to find the solution. We also apply our height reduction lemma to the algorithm provided in Adjiashvili et al. (2019) plus a more careful analysis to improve their 12-approximation and provide a polynomial time ( 5 + ϵ )-approximation. [ABSTRACT FROM AUTHOR]