Search

Dimension reduction is a technique used to transform data from a high-dimensional space into a lower-dimensional space, aiming to retain as much of the original information as possible. This approach is crucial in many disciplines like engineering, biology, astronomy, and economics. In this paper, we consider the following dimensionality reduction instance: Given an n-dimensional probability distribution p and an integer m < n , we aim to find the m-dimensional probability distribution q that is the closest to p, using the Kullback–Leibler divergence as the measure of closeness. We prove that the problem is strongly NP-hard, and we present an approximation algorithm for it. [ABSTRACT FROM AUTHOR]

In this work we investigate the min-max-min robust optimization problem and the k-adaptability robust optimization problem for binary problems with uncertain costs. The idea of the first approach is to calculate a set of k feasible solutions which are worst-case optimal if in each possible scenario the best of the k solutions is implemented. It is known that the min-max-min robust problem can be solved efficiently if k is at least the dimension of the problem, while it is theoretically and computationally hard if k is small. However, nothing is known about the intermediate case, i.e., k lies between one and the dimension of the problem. We approach this open question and present an approximation algorithm which achieves good problem-specific approximation guarantees for the cases where k is close to or a fraction of the dimension. The derived bounds can be used to show that the min-max-min robust problem is solvable in oracle-polynomial time under certain conditions even if k is smaller than the dimension. We extend the previous results to the robust k-adaptability problem. As a consequence we can provide bounds on the number of necessary second-stage policies to approximate the exact two-stage robust problem. We derive an approximation algorithm for the k-adaptability problem which has similar guarantees as for the min-max-min problem. Finally, we test both algorithms on knapsack and shortest path problems. The experiments show that both algorithms calculate solutions with relatively small optimality gap in seconds. [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 study the investment incentives created by truthful mechanisms that allocate resources using approximation algorithms. Some approximation algorithms guarantee nearly 100% of the optimal welfare in the allocation problem but guarantee nothing when accounting for investment incentives. An algorithm's allocative and investment guarantees coincide if and only if its confirming negative externalities are sufficiently small. We introduce fast approximation algorithms for the knapsack problem that have no confirming negative externalities and guarantees close to 100% for both allocation and investment. [ABSTRACT FROM AUTHOR]

In malleable job scheduling, jobs can be executed simultaneously on multiple machines with the processing time depending on the number of allocated machines. In this setting, jobs are required to be executed non-preemptively and in unison, in the sense that they occupy, during their execution, the same time interval over all the machines of the allocated set. In this work, we study generalizations of malleable job scheduling inspired by standard scheduling on unrelated machines. Specifically, we introduce a general model of malleable job scheduling, where each machine has a (possibly different) speed for each job, and the processing time of a job j on a set of allocated machines S depends on the total speed of S with respect to j. For machines with unrelated speeds, we show that the optimal makespan cannot be approximated within a factor less than e e - 1 , unless P = N P . On the positive side, we present polynomial-time algorithms with approximation ratios 2 e e - 1 for machines with unrelated speeds, 3 for machines with uniform speeds, and 7/3 for restricted assignments on identical machines. Our algorithms are based on deterministic LP rounding. They result in sparse schedules, in the sense that each machine shares at most one job with other machines. We also prove lower bounds on the integrality gap of 1 + φ for unrelated speeds (φ is the golden ratio) and 2 for uniform speeds and restricted assignments. To indicate the generality of our approach, we show that it also yields constant factor approximation algorithms for a variant where we determine the effective speed of a set of allocated machines based on the L p norm of their speeds. [ABSTRACT FROM AUTHOR]

The new iterative method of approximating the boundary trajectory of a short-focus electron beam propagating in a free drift mode in a low-pressure ionized gas under the condition of compensation of the space charge of electrons is considered and discussed in the article. To solve the given approximation task, the root-polynomial functions of the fourth and fifth order were applied, the main features of which are the ravine character and the presence of one global minimum. As an initial approach to solving the approximation problem, the values of the polynomial coefficients are calculated by solving the interpolation problem. After this, the approximation task is solved iteratively. All necessary polynomial coefficients are calculated multiple times, taking into account the values of the function and its derivative at the reference points. The final values of polynomial coefficients of high-order root-polynomial functions are calculated using the dichotomy method. The article also provides examples of the applying fourth-order and fifth-order root-polynomial functions to approximate sets of numerical data that correspond to the description of ravine functions. The obtained theoretical results are interesting and important for the experts who study the physics of electron beams and design modern industrial electron beam technological equipment. [ABSTRACT FROM AUTHOR]

In this paper, we consider a variant of dominating set problem, i.e., the total dominating set problem. Given an undirected graph G = (V , E) , a subset of vertices T ⊆ V is called a total dominating set if every vertex in V is adjacent to at least one vertex in T. Based on LP relaxation techniques, this paper gives a distributed approximation algorithm for the total dominating set problem in general graphs. The presented algorithm obtains a fractional total dominating set that is, at most, k (1 + Δ 1 k) Δ 1 k times the size of the optimal solution to this problem, where k is a positive integer and Δ is the maximum degree of G. The running time of this algorithm is constant communication rounds under the assumption of a synchronous communication model. [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]

Robin Thomas asked whether for every proper minor-closed class G , there exists a polynomial-time algorithm approximating the chromatic number of graphs from G up to a constant additive error independent on the class G. We show this is not the case: unless P = NP , for every integer k ≥ 1 , there is no polynomial-time algorithm to color a K 4 k + 1 -minor-free graph G using at most χ (G) + k − 1 colors. More generally, for every k ≥ 1 and 1 ≤ β ≤ 4 / 3 , there is no polynomial-time algorithm to color a K 4 k + 1 -minor-free graph G using less than β χ (G) + (4 − 3 β) k colors. As far as we know, this is the first non-trivial non-approximability result regarding the chromatic number in proper minor-closed classes. Furthermore, we give somewhat weaker non-approximability bound for K 4 k + 1 -minor-free graphs with no cliques of size 4. On the positive side, we present additive approximation algorithm whose error depends on the apex number of the forbidden minor, and an algorithm with additive error 6 under the additional assumption that the graph has no 4-cycles. [ABSTRACT FROM AUTHOR]

Pareto frontiers of bicriteria continuous convex problems can be efficiently computed and optimal theoretical performance bounds have been established. In the case of bicriteria mixed-integer problems, the approximation of the Pareto frontier becomes, however, significantly harder. In this paper, we propose a new algorithm for approximating the Pareto frontier of bicriteria mixed-integer programs with convex constraints. Such Pareto frontiers are composed of patches of solutions with shared assignments for the discrete variables. By adaptively creating such a patchwork, our algorithm is able to create approximations that converge quickly to the true Pareto frontier. As a quality measure, we use the difference in hypervolume between the approximation and the true Pareto frontier. At least a certain number of patches is required to obtain an approximation with a given quality. This patch complexity gives a lower bound on the number of required computations. We show that our algorithm performs a number of optimization steps that are of a similar order as this lower bound. We provide an efficient MIP-based implementation of this algorithm. The efficiency of our algorithm is illustrated with numerical results showing that our algorithm has a strong theoretical performance guarantee while being competitive with other state-of-the-art approaches in practice. [ABSTRACT FROM AUTHOR]

Background: Scaffolding is a bioinformatics problem aimed at completing the contig assembly process by determining the relative position and orientation of these contigs. It can be seen as a paths and cycles cover problem of a particular graph called the "scaffold graph". Results: We provide some NP-hardness and inapproximability results on this problem. We also adapt a greedy approximation algorithm on complete graphs so that it works on a special class aiming to be close to real instances. The described algorithm is the first polynomial-time approximation algorithm designed for this problem on non-complete graphs. Conclusion: Tests on a set of simulated instances show that our algorithm provides better results than the version on complete graphs. [ABSTRACT FROM AUTHOR]

Consider an information diffusion process on a graph G that starts with k > 0 burnt vertices, and at each subsequent step, burns the neighbors of the currently burnt vertices, as well as k other unburnt vertices. The k-burning number of G is the minimum number of steps b k (G) such that all the vertices can be burned within b k (G) steps. Note that the last step may have smaller than k unburnt vertices available, where all of them are burned. The 1-burning number coincides with the well-known burning number problem, which was proposed to model the spread of social contagion. The generalization to k -burning number allows us to examine different worst-case contagion scenarios by varying the spread factor k. In this paper we prove that computing k -burning number is APX-hard, for any fixed constant k. We then give an O ((n + m) log ⁡ n) -time 3-approximation algorithm for computing k -burning number, for any k ≥ 1 , where n and m are the number of vertices and edges, respectively. Finally, we show that even if the burning sources are given as an input, computing a burning sequence itself is an NP-hard problem. [ABSTRACT FROM AUTHOR]

We introduce a new graph-theoretic concept in the area of network monitoring. A set M of vertices of a graph G is a distance-edge-monitoring set if for every edge e of G , there are a vertex x of M and a vertex y of G such that e belongs to all shortest paths between x and y. We denote by dem (G) the smallest size of such a set in G. The vertices of M represent distance probes in a network modeled by G ; when the edge e fails, the distance from x to y increases, and thus we are able to detect the failure. It turns out that not only we can detect it, but we can even correctly locate the failing edge. In this paper, we initiate the study of this new concept. We show that for a nontrivial connected graph G of order n , 1 ≤ dem (G) ≤ n − 1 with dem (G) = 1 if and only if G is a tree, and dem (G) = n − 1 if and only if it is a complete graph. We compute the exact value of dem for grids, hypercubes, and complete bipartite graphs. Then, we relate dem to other standard graph parameters. We show that dem (G) is lower-bounded by the arboricity of the graph, and upper-bounded by its vertex cover number. It is also upper-bounded by twice its feedback edge set number. Moreover, we characterize connected graphs G with dem (G) = 2. Then, we show that determining dem (G) for an input graph G is an NP-complete problem, even for apex graphs. There exists a polynomial-time logarithmic-factor approximation algorithm, however it is NP-hard to compute an asymptotically better approximation, even for bipartite graphs of small diameter and for bipartite subcubic graphs. For such instances, the problem is also unlikely to be fixed parameter tractable when parameterized by the solution size. [ABSTRACT FROM AUTHOR]

The ever increasing technological demand for the DFT computation poses several challenges both to theory and hardware realization. The design of usual fast Fourier transform (FFT) algorithms seems to have reached a stage of diminishing returns in terms of performance. Alternatively, approximate transform methods have been demonstrated to provide substantial gains in terms of energy-efficiency and performance by tolerating small inaccuracies in the results. In this letter, we present a transform scaling method variant of the Cooley-Tukey algorithm to obtain DFT approximations of large blocksize. The proposed method scales up a given $N$ -point transformation to an $N^{2}$ -point transformation. Such scaling can be successively applied leading to $N^{2^{n}}$ -point transformations. We have fully presented the $32^{4}$ -point DFT approximation which stems from a multiplierless 32-point DFT approximation. The proposed approximation is equipped with a fast algorithm; we also supply the arithmetic complexity assessment and an error analysis. [ABSTRACT FROM AUTHOR]

A weak conical greedy algorithm is introduced with respect to an arbitrary positive complete dictionary in a Hilbert space; this algorithm gives an approximation of an arbitrary space element by a combination of dictionary elements with nonnegative coefficients. The convergence of this algorithm is proved and an estimate of the convergence rate for the elements of the convex hull of the dictionary is given. [ABSTRACT FROM AUTHOR]

A recent paper by Schulze et al. (Math Methods Oper Res 92(1):107–132, 2020) presented the Rectangular Knapsack Problem (Rkp) as a crucial subproblem in the study on the Cardinality-constrained Bi-objective Knapsack Problem (Cbkp). To this end, they started an investigation into its complexity and approximability. The key results are an NP -hardness proof for a more general scenario than Rkp, and a 4.5-approximation for Rkp, raising the question of improvements for either result. In this note we settle both questions conclusively: we show that (a) Rkp is indeed NP -hard in the considered setting (and even in more restricted settings), and (b) there exists both a pseudopolynomial algorithm and a fully-polynomial time approximation scheme (i.e., efficient approximability within any desired ratio α > 1 ) for Rkp. [ABSTRACT FROM AUTHOR]

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

Given a set of players P, a set of indivisible resources R, and a set of non-negative values { v pr } p ∈ P , r ∈ R , an allocation is a partition of R into disjoint subsets { C p } p ∈ P so that each player p is assigned the resources in C p . The max-min fair allocation problem is to determine the allocation that maximizes min p ∑ r ∈ C p v pr . In the restricted case of this problem, each resource r has an intrinsic value v r , and v pr = v r for every player p who desires r and v pr = 0 for every player p who does not. We study the restricted max-min fair allocation problem in this paper. For this problem, the configuration LP has played an important role in estimating and approximating the optimal solution. Our first result is an upper bound of 3 21 26 on the integrality gap, which is currently the best. It is obtained by a tighter analysis of the local search of Asadpour et al. [TALG'12]. It remains unknown whether this local search runs in polynomial time or not. Our second result is a polynomial-time algorithm that achieves an approximation ratio of 4 + δ for any constant δ ∈ (0 , 1) . Our algorithm can be seen as a generalization of the aforementioned local search. [ABSTRACT FROM AUTHOR]

k-median with service installation costs is a frequently encountered problem in applications involving multiple service requirements, which generalizes the standard k -median problem in that each client is associated with a specific service and can only be connected to the facilities where the service is installed. In this paper, we give a (13.349 + ϵ) -approximation algorithm for the k -median with service installation costs problem, improving upon the previous best approximation ratio of 18. We propose a new deterministic rounding approach to deal with the challenges caused by the service requirements, which is the crucial step in getting the improved ratio. • We give a (13.349 + ϵ) -approximation algorithm for the k -median with service installation costs problem. • We obtain a well-behaved fractional solution to the problem based on the framework of Lagrangian relaxation. • We give a new deterministic rounding approach to deal with the challenges caused by the service requirements. [ABSTRACT FROM AUTHOR]

Online social networks have become major battlegrounds for political campaigns, viral marketing, and the dissemination of news. As a consequence, “bad actors” are increasingly exploiting these platforms, which is a key challenge for their administrators, businesses and society in general. The spread of fake news is a classical example of the abuse of social networks by these bad actors. While some have advocated for stricter policies to control the spread of misinformation in social networks, this often happens in detriment of their democratic and organic structure. In this paper, we aim to limit the influence of a target group in a social network via the removal of a few users/links. We formulate the influence limitation problem in a data-driven fashion, by taking into account past propagation traces. More specifically, our algorithms find critical edges to be removed in order to decrease the influence of a target group based on past data. The idea is to control the diffusion processes while minimizing the amount of disturbance in the network structure. Moreover, we consider two types of constraints over edge removals, a budget constraint and also a, more general, set of matroid constraints. These problems lead to interesting challenges in terms of algorithm design. For instance, we are able to show that influence limitation is APX-hard and propose deterministic and probabilistic approximation algorithms for the budgeted and the matroid version of the problem, respectively. Experiments show that the proposed approaches outperform several baselines. [ABSTRACT FROM AUTHOR]

Metric data plays an important role in various settings, for example, in metric-based indexing, clustering, classification, and approximation algorithms in general. Due to measurement error, noise, or an inability to completely gather all the data, a collection of distances may not satisfy the basic metric requirements, most notably the triangle inequality. In this paper we initiate the study of the metric violation distance problem: given a set of pairwise distances, modify the minimum number of distances such that the resulting set forms a metric. Three variants of the problem are considered, based on whether distances are allowed to only decrease, only increase, or the general case which allows both decreases and increases. We show that while the decrease only variant is polynomial time solvable, the increase only and general variants are NP-Complete, and moreover cannot in polynomial time be approximated to any ratio better than the minimum vertex cover problem. We then provide approximation algorithms for the increase only and general variants of the problem, by proving interesting necessary and sufficient conditions on the optimal solution, which are used to approximately reduce to a purely combinatorial problem for which we provide matching asymptotic upper and lower bounds. [ABSTRACT FROM AUTHOR]

Directed Steiner Tree (DST) is a central problem in combinatorial optimization and theoretical computer science: Given a directed graph G = (V , E) with edge costs c ∈ R ≥ 0 E , a root r ∈ V and k terminals K ⊆ V , we need to output the minimum-cost arborescence in G that contains an r → t path for every t ∈ K . Recently, Grandoni, Laekhanukit and Li, and independently Ghuge and Nagarajan, gave quasi-polynomial time O (log 2 k / log log k) -approximation Algorithms for the problem, which are tight under popular complexity assumptions. In this paper, we consider the more general Degree-Bounded Directed Steiner Tree (DB-DST) problem, where we are additionally given a degree bound d v on each vertex v ∈ V , and we require that every vertex v in the output tree has at most d v children. We give a quasi-polynomial time (O (log n log k) , O (log 2 n)) -bicriteria approximation: The Algorithm produces a solution with cost at most O (log n log k) times the cost of the optimum solution that violates the degree constraints by at most a factor of O (log 2 n) . This is the first non-trivial result for the problem. While our cost-guarantee is nearly optimal, the degree violation factor of O (log 2 n) is an O (log n) -factor away from the approximation lower bound of Ω (log n) from the set-cover hardness. The hardness result holds even on the special case of the Degree-Bounded Group Steiner Tree problem on trees (DB-GST-T). With the hope of closing the gap, we study the question of whether the degree violation factor can be made tight for this special case. We answer the question in the affirmative by giving an (O (log n log k) , O (log n)) -bicriteria approximation Algorithm for DB-GST-T. [ABSTRACT FROM AUTHOR]

The piecewise monotonic approximation problem makes the least changes to n univariate noisy data so that the piecewise linear interpolant to the new values is composed of at most k monotonic sections. The term "least changes" is defined in the sense of a global sum of strictly convex functions of changes. The main difficulty in this calculation is that the extrema of the interpolant have to be found automatically, but the number of all possible combinations of extrema can be O (n k - 1) , which makes not practicable to test each one separately. It is known that the case k = 1 is straightforward, and that the case k > 1 reduces to partitioning the data into at most k disjoint sets of adjacent data and solving a k = 1 problem for each set. Some ordering relations of the extrema are studied that establish three quite efficient algorithms by using a binary search method for partitioning the data. In the least squares case the total work is only O (n σ + k σ log 2 σ) computer operations when k ≥ 3 and is only O (n) when k = 1 or 2, where σ - 2 is the number of sign changes in the sequence of the first differences of the data. Fortran software has been written for this case and the numerical results indicate superior performance to existing algorithms. Some examples with real data illustrate the method. Many applications of the method arise from bioinformatics, energy, geophysics, medical imaging, and peak finding in spectroscopy, for instance. [ABSTRACT FROM AUTHOR]

Graph summarization is beneficial in a wide range of applications, such as visualization, interactive and exploratory analysis, approximate query processing, reducing the on-disk storage footprint, and graph processing in modern hardware. However, the bulk of the literature on graph summarization surprisingly overlooks the possibility of having edges of different types. In this article, we study the novel problem of producing summaries of multi-relation networks, i.e., graphs where multiple edges of different types may exist between any pair of nodes. Multi-relation graphs are an expressive model of real-world activities, in which a relation can be a topic in social networks, an interaction type in genetic networks, or a snapshot in temporal graphs. The first approach that we consider for multi-relation graph summarization is a two-step method based on summarizing each relation in isolation, and then aggregating the resulting summaries in some clever way to produce a final unique summary. In doing this, as a side contribution, we provide the first polynomial-time approximation algorithm based on the k-Median clustering for the classic problem of lossless single-relation graph summarization. Then, we demonstrate the shortcomings of these two-step methods, and propose holistic approaches, both approximate and heuristic algorithms, to compute a summary directly for multi-relation graphs. In particular, we prove that the approximation bound of k-Median clustering for the single relation solution can be maintained in a multi-relation graph with proper aggregation operation over adjacency matrices corresponding to its multiple relations. Experimental results and case studies (on co-authorship networks and brain networks) validate the effectiveness and efficiency of the proposed algorithms. [ABSTRACT FROM AUTHOR]

Sweep coverage plays an important role in many applications such as data gathering, sensing coverage and devices control. In this paper, we deal with the cooperative sweep coverage problem with multiple mobile sensors to periodically cover all positions of interest (PoIs) in the surveillance region. Different from traditional sweep coverage scenarios, the cooperative sweep coverage (CSC) problem allows the deployment of multiple sensors on the same trajectory to further reduce the sweep period or detection delay. We also consider the multi-sink sweep coverage (MSSC) problem where each mobile sensor must periodically transmit its collected data to a base station due to the limited storage capacity and power supply. Correspondingly, we propose two constant-factor approximations, namely ${{CoCycle}}$ C o C y c l e and ${{SinkCycle}}$ S i n k C y c l e , to minimize the maximum sweep period for these two problems. The approximation ratios of ${{CoCycle}}$ C o C y c l e and ${{SinkCycle}}$ S i n k C y c l e are proved to be 4 and 6 respectively. As far as we know, ${{SinkCycle}}$ S i n k C y c l e is the first approximation for the sweep coverage problem with multiple sinks. We also provide two optimal algorithms for the CSC problem in one dimensional case and a useful insight regarding the MSSC problem with only one available sink. Finally, we conduct various numerical experiments to validate the effectiveness and efficiency of our designs. [ABSTRACT FROM AUTHOR]

The Maximum Vertex Coverage problem (abbreviated as MVC) is to maximum the number of edges covered by a set of vertices of size exactly K on a graph. This problem is the dual of the vertex cover problem and has attracted a lot of interests in the literature of approximation algorithm. So far, the best approximation factor for the MVC problem is 3/4, which is obtained using an LP-rounding method. The main results of this paper are new approximation algorithms for MVC on cubic graphs and 3-bounded graphs (the vertex degrees are at most 3). The approximation factor on cubic graphs is 79/90 (≈0.878), which is tight by analyzing the existence of a feasible solution for a linear programming system. This algorithm can also be extended to 3-bounded graphs and guarantees an approximation factor of 19/24 (≈0.792). [ABSTRACT FROM AUTHOR]

We present a framework for approximating the metric TSP based on a novel use of matchings. Traditionally, matchings have been used to add edges to make a given graph Eulerian, whereas our approach also allows for the removal of certain edges leading to a decreased cost. For the TSP on graphic metrics (graph-TSP), we show that the approach gives a 1.461-approximation algorithm with respect to the Held-Karp lower bound. For graph-TSP restricted either to half-integral solutions to the Held-Karp relaxation or to a class of graphs that contains subcubic and claw-free graphs, we show that the integrality gap of the Held-Karp relaxation matches the conjectured ratio 4/3. The framework also allows for generalizations in a natural way and leads to analogous results for the s, t-path traveling salesman problem on graphic metrics where the start and end vertices are prespecified. [ABSTRACT FROM AUTHOR]

The problem of minimizing the makespan on parallel identical machines is considered in the presence of additional resources, provided that some jobs at any time of their processing require one unit of a particular resource. We establish a lower bound on the worst-case performance of any group technology algorithm, which schedules the composite jobs formed of the original jobs that require the same resource. A simple group technology algorithm is given such that in the worst case no group technology algorithm performs better. An algorithm for the two-machine case is presented which guarantees a tight worst-case performance ratio of 6/5. [ABSTRACT FROM AUTHOR]

In a software defined network, the controller needs to obtain/collect traffic measurement information (i.e., flow statistics) from switches for different applications, such as traffic engineering. Existing solutions seldom consider the per-switch cost, which may lead to heavy statistics collection cost (e.g., high CPU overhead) on some switches. Due to limited computing power on most commodity switches, heavy statistics collection cost on those switches may seriously interfere with the basic rule operations, especially when some switches need to deal with many new-arrival flows or update routes of existing flows. To address this challenge, we design and implement efficient flow statistics collection (FSC) with limited interference on the basic rule operations. We formally propose a cooperative flow statistics collection with per-switch cost constraint (CP-FSC) problem. We prove that the CP-FSC problem is NP-hard and present an efficient algorithm with approximation ratio 1/2, based on dynamic programming. To reduce the time complexity, a greedy-based algorithm with approximation ratio 1/3 is also presented. We implement the proposed FSC algorithms on our SDN platform. The experimental results and the extensive simulation results show 36%-59% performance improvement compared with the existing solutions. [ABSTRACT FROM AUTHOR]

The red-blue median problem considers a set of red facilities, a set of blue facilities, and a set of clients located in some metric space. The goal is to open k r red facilities and k b blue facilities such that the sum of the distance from each client to its nearest opened facility is minimized, where k r , k b ≥ 0 are two given integers. Designing approximation algorithms for this problem remains an active area of research due to its applications in various fields. However, in many applications, the existence of noisy data poses a big challenge for the problem. In this paper, we consider the prize-collecting red-blue median problem, where the noisy data can be removed by paying a penalty cost. The current best approximation guarantee for the prize-collecting red-blue median problem is a ratio of 24, which was obtained by LP-rounding. We deal with this problem using a local search algorithm. We construct a layered structure of the swap pairs, which yields a (9 + ϵ) -approximation for the prize-collecting red-blue median problem. Our techniques generalize to a more general prize-collecting τ-color median problem, where the facilities have τ different types, and give a (4 τ + 1 + ϵ) -approximation for the case where τ is a constant. • We give a (9 + ϵ) -approximation for prize-collecting red-blue median, which improves the current best approximation ratio of 24. • Our techniques generalize to prize-collecting τ -color median, and yield a (4 τ + 1 + ϵ) -approximation. • We give a novel method for analyzing local search algorithms that yields layered swap pairs. [ABSTRACT FROM AUTHOR]

In this paper, we suggest basing the development of classification methods on traditional techniques but approximating them in whole or in part with artificial neural networks (ANNs). Compared to a direct ANN approach, the underlying traditional method is often easier to analyse. Classification failures can be better understood and corrected for, while at the same time faster execution can be obtained due to the parallel ANN structure. Furthermore, such a two‐step design philosophy partly eliminates the 'guesswork' associated with the design of ANNs. The expected gain is thus that the benefits from the traditional field, and the ANN field can be obtained by combining the best features from both fields. We illustrate our approach by working through an explicit example, namely, a Nearest Neighbour classifier applied to a subset of the MNIST database of handwritten digits. Two different approaches are discussed for how to translate the traditional method into an ANN. The first approach is based on a constructive implementation which directly reflects the original algorithm. The second approach uses ANNs to approximate the whole, or part of, the original method. An important part of the approach is to show how improvements can be introduced. In line with the presented philosophy, this is done by extending the traditional method in several ways followed by ANN approximation of the modified algorithms. The extensions are based on a windowed version of the nearest neighbour algorithm. We show that the improvements carry over to the ANN implementations. We further investigate the stability of the solutions by modifying the training set. It is shown that the errors do not change significantly. This also holds true for the ANN approximations providing confidence that the two‐step strategy is robust. [ABSTRACT FROM AUTHOR]

We develop new approximation algorithms for classical graph and set problems in the RAM model under space constraints. As one of our main results, we devise an algorithm for d - H I T T I N G S E T that runs in time n O (d 2 + (d / ϵ)) , uses O ((d 2 + (d / ϵ)) log n) bits of space, and achieves an approximation ratio of O ((d / ϵ) n ϵ) for any positive ϵ ≤ 1 and any d ∈ N . In particular, this yields a factor- O (log n) approximation algorithm which runs in time n O (log n) and uses O (log 2 n) bits of space (for constant d). As a corollary, we obtain similar bounds for V E R T E X C O V E R and several graph deletion problems. For bounded-multiplicity problem instances, one can do better. We devise a factor-2 approximation algorithm for V E R T E X C O V E R on graphs with maximum degree Δ , and an algorithm for computing maximal independent sets, both of which run in time n O (Δ) and use O (Δ log n) bits of space. For the more general d - H I T T I N G S E T problem, we devise a factor-d approximation algorithm which runs in time n O (d δ 2) and uses O (d δ 2 log n) bits of space on set families where each element appears in at most δ sets. For I N D E P E N D E N T S E T restricted to graphs with average degree d, we give a factor-(2d) approximation algorithm which runs in polynomial time and uses O (log n) bits of space. We also devise a factor- O (d 2) approximation algorithm for D O M I N A T I N G S E T on d-degenerate graphs which runs in time n O (log n) and uses O (log 2 n) bits of space. For d-regular graphs, we show how a known randomized factor- O (log d) approximation algorithm can be derandomized to run in time n O (1) and use O (log n) bits of space. Our results use a combination of ideas from the theory of kernelization, distributed algorithms and randomized algorithms. [ABSTRACT FROM AUTHOR]

We study robust solutions for combinatorial optimization problems with budgeted uncertainty sets in the min–max–min setting, where the decision maker is allowed to choose a set of k different solutions from which one can be chosen after the uncertain scenario has been revealed. We first show how the problem can be decomposed into polynomially many subproblems if k is fixed. We then consider the special case where k = 2 , i.e., one is allowed to choose two different solutions to hedge against the uncertainty. Using the decomposition, we provide polynomial-time algorithms for the unconstrained combinatorial optimization problem, the matroid maximization problem, the selection problem, and the shortest path problem on series–parallel graphs. The shortest path problem on general graphs turns out to be NP -hard. We show how to transform approximation algorithms for minimization subproblems to approximation algorithms for the robust problem and study the knapsack problem to show that this does not hold for maximization problems in general. We present a PTAS for the corresponding subproblem and prove that the min–max–min knapsack problem with k = 2 is not approximable at all. [ABSTRACT FROM AUTHOR]

Offset curves are one of the crucial curves, but the presence of square root function in the representation is main hindrance towards their applications in CAD/CAM. The presented technique is based on offset approximation using rational trigonometric B'ezier curves. The idea is to construct a new control polygon parallel to original one. The two end points of the offset control polygon have been taken as exact offset end points, while the middle control points and weights have been computed using definition of parallel curves. As a result, offsets of rational and nonrational trigonometric B'ezier curves have been approximated by rational cubic trigonometric B'ezier curve. An error between exact and approximated offset curves have also been computed to show the efficacy of the method. [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]

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]

This paper considers the approximation of the infinite-horizon value function of the continuous-time switched linear quadratic regulator (LQR) problem. We propose a two successive approximation approach to achieving arbitrarily high accuracy. The infinite-horizon value function is first approximated by a finite-horizon value function, and the resulting truncation error is shown to converge to zero exponentially as the length of the control horizon increases. Then, the finite-horizon value function is approximated through a uniform discretization of the switched linear system, and the approximation error is proven to be proportional to the discretization step. These theoretical results facilitate the development of an efficient approximation algorithm, which further results in a near-optimal control policy. Compared with the existing methods, our algorithm obviates numerical issues induced by singular optimal control. Two numerical examples are presented to illustrate the effectiveness of our algorithm. [ABSTRACT FROM AUTHOR]

The transportation problem is a fundamental problem in operations research, where items need to be transported from supply nodes (each with a given supply) to demand nodes (each with a given demand) in the cheapest possible way. Here, we are interested in a generalization of the transportation problem where, each supply node has a (possibly empty) set of conflicting pairs of demand nodes, and each demand node a (possibly empty) set of conflicting pairs of supply nodes. Each supply node may only send supply to at most one demand node of each conflicting pair. Likewise, each demand node may only receive supply from at most one supply node of each conflicting pair. We call the resulting problem the transportation problem with conflicts (TPC). We show that the complexity of TPC depends upon the structure of the so-called conflict graph that follows from the conflicting pairs. More concrete, we show that for many graph-classes the corresponding TPC remains NP-hard, and for some special cases we derive constant factor approximation algorithms. [ABSTRACT FROM AUTHOR]

• Improved approximation algorithm for Budgeted Connected Dominating Set. • Optimal approximation algorithm for Budgeted Star Dominating Set. • Optimal approximation algorithm for Budgeted Edge-Vertex Domination. We consider the Budgeted version of the classical Connected Dominating Set problem (BCDS). Given a graph G and a budget k , we seek a connected subset of at most k vertices maximizing the number of dominated vertices in G. We improve over the previous (1 − e − 1) / 13 state of the art [Khuller, Purohit, and Sarpatwar, SODA 2014 by introducing a new method for performing tree decompositions in the analysis of the algorithm. This new approach provides a (1 − e − 1) / 12 approximation guarantee. By generalizing the analysis, we are able to obtain a further improvement to (1 − e − 7 / 8) / 11. On the other hand, we prove a (1 − e − 1 + ϵ) inapproximability bound, for any ϵ > 0 , holding also if the subset is required to have a star as a subgraph. In the latter case, we design another algorithm with a matching (1 − e − 1) approximation guarantee. Also, we examine the edge-vertex domination variant, where an edge dominates its endpoints and all vertices neighboring them. In Budgeted Edge-Vertex Domination (BEVD), we seek a (not necessarily connected) subset of k edges maximizing the number of dominated vertices in G. We prove a (1 − e − 1) -approximation and a (1 − e − 1 + ϵ) -inapproximability by reductions to/from the maximum coverage problem. Finally, we study the "dual" Partial Edge-Vertex Domination (PEVD) problem, and we present a log-approximation by a reduction to the partial cover problem. [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 consider scheduling on identical and unrelated parallel machines with job assignment restrictions. These problems are NP-hard and they do not admit polynomial time approximation algorithms with approximation ratios smaller than 1.5 unless P=NP. However, if we impose limitations on the set of machines that can process a job, the problem sometimes becomes easier in the sense that algorithms with approximation ratios better than 1.5 exist. We introduce a graph framework based on the assignment restrictions and study the computational complexity of the scheduling problem with respect to structural properties of the resulting graphs, in particular, their tree- and cliquewidth. We identify cases that admit polynomial time approximation schemes or FPT algorithms generalizing and extending previous results in this area. [ABSTRACT FROM AUTHOR]

This work deals with the robust maximum weighted independent set problem, i.e. finding a subset of graph vertices that are not adjacent to each other and whose sum of weights is as large as possible. Uncertainty in problem formulation is restricted to vertex weights and expressed explicitly by a finite set of scenarios. Three criteria of robustness are considered: absolute robustness (max-min), robust deviation (min-max regret), and relative robustness (relative min-max regret). Since the conventional maximum weighted independent set problem is already NP-hard, finding the exact solution of its robust counterpart should obviously have a prohibitive computational complexity. Therefore, we propose an approximate algorithm for solving the considered robust problem, which is based on evolutionary computing and on various crossover and mutation operators. The algorithm is experimentally evaluated on appropriate problem instances. It is shown that satisfactory solutions can be obtained for any of the three robustness criteria in reasonable time. [ABSTRACT FROM AUTHOR]

This paper proposes a scheduling model for the washing step of medical device sterilization. After use in a surgery, medical devices pass through several steps where the washing is usually a bottleneck. We study the cases of external and internal sterilization services to minimize two objectives: makespan and flow time of washing operations. First, we study internal sterilization services considering jobs can have different or unit sizes. For these two cases, we provide a mixed integer linear model and a dynamic programming model, and integrate these methods in an ϵ -constraint model. For the case of external services, first we develop a simultaneous (2, 2) approximation algorithm and then derive an algorithmic scheme to generate a partial 2-approximation of the Pareto set. Several numerical experiments are conducted to demonstrate the strength of proposed solution methods. [ABSTRACT FROM AUTHOR]

Traffic measurement is very important for various applications, such as traffic engineering and attack detection, in software-defined networks. Due to limited resources (e.g., computing, memory) on SDN switches, sketches have been widely used for efficient traffic measurement. Meanwhile, multiple independent sketches are required for different application requirements, such as heavy hitter detection and flow size distribution estimation. To avoid the measurement redundancy, we configure which sketch(es) will measure flow on each switch. If traffic measurement is performed on each switch without considering network routing, due to traffic dynamics, it will cause massive measurement overhead on a switch, which may exceed the switch’s computing capacity. In this paper, we study the joint optimization of flow routing and sketch configuration in SDNs. We formulate this problem as an integer linear programming and prove its NP-hardness. To solve this problem, we propose a rounding-based offline algorithm and a primal-dual-based online algorithm for different application scenarios. To deal with bursty traffic, we also design an adaptive sampling mechanism for high-fidelity traffic measurement. We formally analyze the approximation performance or competitive ratio of the proposed algorithms. The extensive simulation results show the high efficiency of our proposed algorithms. For example, the online algorithm can improve the network throughput 30% compared with the state-of-the-art. [ABSTRACT FROM AUTHOR]

In the multiway cut problem, we are given an undirected graph with non-negative edge weights and a collection of k terminal nodes, and the goal is to partition the node set of the graph into k non-empty parts each containing exactly one terminal, so that the total weight of the edges crossing the partition is minimized. The multiway cut problem for k ≥ 3 is APX-hard. For arbitrary k, the best-known approximation factor is 1.2965 due to Sharma and Vondrák (Proceedings of the forty-sixth annual ACM symposium on theory of computing, STOC, 2014) while the best known inapproximability result due to Angelidakis et al. (Integer programming and combinatorial optimization, IPCO, 2017) rules out efficient algorithms to achieve an approximation factor less than 1.2 under the unique games conjecture (UGC). In this work, we improve the lower bound to 1.20016 under UGC by constructing an integrality gap instance for the CKR relaxation. The CKR relaxation embeds the graph into a simplex and it is known that its integrality gap translates to inapproximability under UGC. A technical challenge in improving the integrality gap has been the lack of geometric tools to understand higher-dimensional simplices. Our instance is a non-trivial 3-dimensional instance that overcomes this technical challenge. We analyze the gap of the instance by viewing it as a convex combination of 2-dimensional instances and a uniform 3-dimensional instance. We believe that this technique could be exploited further to construct instances with larger integrality gap. One of the ingredients of our proof technique is a generalization of a result on Sperner admissible labelings due to Mirzakhani and Vondrák (Proceedings of the twenty-sixth annual ACM-SIAM symposium on discrete algorithms, SODA, 2015) that might be of independent combinatorial interest. [ABSTRACT FROM AUTHOR]

We study the scheduling problem with calibrations. We are given a set of n jobs that need to be scheduled on a set of m machines. However, a machine can schedule jobs only if a calibration has been performed beforehand and the machine is considered as valid during a fixed time period of T , after which it must be recalibrated before running more jobs. In this paper, we investigate the batch calibrations; calibrations occur in batch and at the same moment. It is then not possible to perform any calibrations during a period of T. We consider different cost function depending on the number of machines we calibrate at a given time, i.e., the cost function is denoted as f (x) where x is the number of calibrations in the batch. Moreover, jobs have release time, deadline, and unit processing time. The objective is to schedule all jobs with the minimum cost of calibrations. We give a dynamic program to solve the case with an arbitrary cost function. Then, we propose several faster approximation algorithms for different cost functions: an optimal algorithm when f (x) = b , a 3-approximation algorithm when f (x) = x and a (m + b) / (b + 1) -approximation algorithm when f (x) = x + b. The running time of these algorithms are O (n 2). [ABSTRACT FROM AUTHOR]

We study the nonuniform capacitated multi-item lot-sizing problem. In this problem, there is a set of demands over a planning horizon of T discrete time periods, and all demands must be satisfied on time. We can place an order at the beginning of each period s, incurring an ordering cost Ks. In this order, we can order up to Cs units of products. On the other hand, carrying inventory from time to time incurs an inventory holding cost. The goal of the problem is to find a feasible solution that minimizes the sum of ordering and holding costs. Levi et al. [Levi R, Lodi A, Sviridenko M (2008) Approximation algorithms for the capacitated multi-item lot-sizing problem via flow-cover inequalities. Math. Oper. Res. 33(2):461–474.] gave a two-approximation for the problem when the capacities Cs are the same. Extending the result to the case of nonuniform capacities requires new techniques as pointed out in the discussion section of their paper. In this paper, we solve the problem by giving a 10-approximation algorithm for the capacitated multi-item lot-sizing problem with general capacities. The constant approximation is achieved by adding an exponential number of new covering inequalities to the natural facility location–type linear programming (LP) relaxation for the problem. Along the way of our algorithm, we reduce the lot-sizing problem to two generalizations of the classic knapsack-covering problem. We give LP-based constant approximation algorithms for both generalizations via the iterative rounding technique. [ABSTRACT FROM AUTHOR]

Nowadays, with the development of micro-electro-mechanical technologies, sweep coverage with mobile sensors is more and more popular in wireless sensor networks, which is also applied widely in other scenarios, such as message ferrying and data routing in ad-hoc networks. In order to reduce the sweep cycle and the number of mobile sensors, we propose the Distance-Sensitive-Route-Scheduling (DSRS) problem, which is to consider the effect of sensing range. We prove that DSRS is NP-hard, and consider three different scenarios: the single sensing-point case, the general case, and the extended case. In the single sensing-point case, we propose an approximation algorithm ROSE to schedule the routes of the mobile sensors efficiently. For the general case and the extended case, we present two other approximation algorithms G-ROSE and E-ROSE based on ROSE. We further characterize the non-locality property and design a distributed algorithm D-ROSE, coordinating sensors to meet the sweep requirements with best effort. Our algorithms are scalable to different sweep coverage problems, and according to the simulation results, they greatly outperform other existing algorithms up to 45 percent especially with a large sensing range. [ABSTRACT FROM AUTHOR]