Search

Network coding (NC), when combined with multipath routing, enables a linear programming (LP) formulation for a multi-source multicast with intra-session network coding (MISNC) problem. However, it is still hard to solve using conventional methods due to the enormous scale of variables or constraints. In this paper, we try to solve this problem in terms of throughput maximization from an algorithmic perspective. We propose a novel formulation based on the extreme flow decomposition technique, which facilitates the design and analysis of approximation and online algorithms. For the offline scenario, we develop a fully polynomial time approximation scheme (FPTAS) which can find a (1 + ω) -approximation solution for any specified ω > 0. For the online scenario, we develop an online primal-dual algorithm which proves O (1) -competitive and violates link capacities by a factor of O (log ⁡ m) , where m is the link number. The proposed algorithms share an elegant primal-dual form and thereby have inherent advantages of simplicity, efficiency, and scalability. To better understand the proposed approach, we devise delicate numerical examples on an extended butterfly network to validate the effects of algorithmic parameters and make an interesting comparison between the offline and online cases. We also perform large-scale simulations on real networks to validate the effectiveness of the proposed FPTAS and online algorithm. • Extreme flow decomposition technique for intra-session network coding. • Offline FPTAS with provable approximation ratio. • Online primal-dual algorithm with provable competitive ratio. • Large-scale experiments using public datasets. [ABSTRACT FROM AUTHOR]

Given a digraph G = (V , E) , the k -path partition problem aims to find a minimum collection of vertex-disjoint directed paths, of order at most k , to cover all the vertices. The problem has various applications. Its special case on undirected graphs is NP-hard when k ≥ 3 , and has received much study recently from the approximation algorithm perspective. However, the general problem on digraphs is seemingly untouched in the literature. We fill the gap with the first k / 2 -approximation algorithm, based on a novel concept of enlarging walk to minimize the number of singletons. Secondly, for k = 3 , we define a second novel kind of enlarging walks to greedily reduce the number of 2-paths in the 3-path partition and propose an improved 13/9-approximation algorithm. Lastly, for any k ≥ 7 , we present an improved (k + 2) / 3 -approximation algorithm built on the maximum path-cycle cover followed by a careful 2-cycle elimination process. [ABSTRACT FROM AUTHOR]

We obtain approximation ratio 4 + 2 ℓ ≈ 4 + 4 lg ⁡ k lg ⁡ n − lg ⁡ k for the (undirected) k -Connected Subgraph problem, where ℓ = ⌊ lg ⁡ n − lg ⁡ k + 1 2 lg ⁡ k + 1 ⌋ is the largest integer such that 2 ℓ − 1 k 2 ℓ + 1 ≤ n. For large values of n this improves the ratio 6 of Cheriyan and Végh [4] when n ≥ k 3 (the case ℓ = 1). Our result implies an fpt-approximation ratio 4 + ϵ that matches (up to the "+ ϵ " term) the best known ratio 4 for k = 6 , 7 for both the general and the easier augmentation versions of the problem. Similar results are shown for the problem of covering an arbitrary symmetric crossing supermodular biset function. [ABSTRACT FROM AUTHOR]

We study clustering problems such as k -Median, k -Means, and Facility Location in graphs of low highway dimension, which is a graph parameter modeling transportation networks. It was previously shown that approximation schemes for these problems exist, which either run in quasi-polynomial time (assuming constant highway dimension) (Feldmann et al., 2018) [8] or run in FPT time (parameterized by the number of clusters k , the highway dimension, and the approximation factor) (Becker et al., 2018; Braverman et al., 2021) [9,10]. In this paper we show that a polynomial-time approximation scheme (PTAS) exists (assuming constant highway dimension). We also show that the considered problems are NP-hard on graphs of highway dimension 1. [ABSTRACT FROM AUTHOR]

In this paper, we study the Maximum Internal Spanning Tree Problem (MIST). Given an undirected simple graph G , the task for the Maximum Internal Spanning Tree problem is to find a spanning tree of G with maximum number of internal vertices. We present an approximation algorithm with performance ratio 4 3 , which improves upon the best known performance ratio 3 2. Our algorithm benefits from a new observation for bounding the number of internal vertices of a spanning tree. We can also give an example to show that the performance ratio 4 3 is actually tight for this algorithm. Finally, we show that MIST is Max-SNP-hard. [ABSTRACT FROM AUTHOR]

Given a graph G with vertex set V , a set S ⊆ V is a secure dominating set of G if S is a dominating set of G and if for every vertex u ∈ V ∖ S , there exists a vertex v ∈ S adjacent to u such that (S ∪ { u }) ∖ { v } is a dominating set of G.The minimum secure dominating set (or, for short, MSDS) problem asks to find an MSDS in a given graph. In this paper, we first show that the decision version of the MSDS problem is NP-complete in unit disk graphs, even in grid graphs. Secondly, we give an O (n + m) time t -approximation algorithm for the MSDS problem in several geometric intersection graphs which are K 1 , t -free for some integer t ≥ 3. Finally, we propose a PTAS for the MSDS problem in unit disk graphs. [ABSTRACT FROM AUTHOR]

Translocation has been long learned as a basic operation to rearrange the structure of a genome. Translocation sorting asks to find a shortest sequence of translocations that transforms one genome into another, which has attracted attention of many scientists in algorithm design. Signed translocation sorting can be solved in polynomial time. Unsigned translocation sorting turns out to be NP-Hard and Max-SNP-Hard. The best known approximation algorithm by now for unsigned translocation sorting can achieve a performance ratio 1.408. In this paper, we propose a new approximation algorithm for unsigned translocation sorting which can achieve a asymptotic performance ratio 1.375. [ABSTRACT FROM AUTHOR]

A graph G = (V , E) is δ -hyperbolic if for any four vertices u , v , w , x , the two larger of the three distance sums d (u , v) + d (w , x) , d (u , w) + d (v , x) , d (u , x) + d (v , w) differ by at most 2 δ ≥ 0. This paper describes the eccentricity terrain of a δ -hyperbolic graph. The eccentricity function e G (v) = max ⁡ { d (v , u) : u ∈ V } partitions vertices of G into eccentricity layers C k (G) = { v ∈ V : e G (v) = r a d (G) + k } , k ∈ N , where r a d (G) = min ⁡ { e G (v) : v ∈ V } is the radius of G. The paper studies the eccentricity layers of vertices along shortest paths, identifying such terrain features as hills, plains, valleys, terraces, and plateaus. It introduces the notion of β -pseudoconvexity, which implies Gromov's ϵ -quasiconvexity, and illustrates the abundance of pseudoconvex sets in δ -hyperbolic graphs. It shows that all sets C ≤ k (G) = { v ∈ V : e G (v) ≤ r a d (G) + k } , k ∈ N , are (2 δ − 1) -pseudoconvex. Several bounds on the eccentricity of a vertex are obtained which yield a few approaches to efficiently approximating all eccentricities. [ABSTRACT FROM AUTHOR]

Truth Discovery is an important learning problem arising in data analytics related fields. It concerns about finding the most trustworthy information from a dataset acquired from a number of unreliable sources. The problem has been extensively studied and a number of techniques have already been proposed. However, all of them are of heuristic nature and do not have any quality guarantee. In this paper, we formulate the problem as a high dimensional geometric optimization problem, called Entropy based Geometric Variance. Relying on a number of novel geometric techniques, we further discover new insights to this problem. We show, for the first time, that the truth discovery problem can be solved with guaranteed quality of solution. Particularly, it is possible to achieve a (1 + ϵ) -approximation within nearly linear time under some reasonable assumptions. We expect that our algorithm will be useful for other data related applications. [ABSTRACT FROM AUTHOR]

Modern, inherently dynamic systems are usually characterized by a network structure which is subject to discrete changes over time. Given a static underlying graph, a temporal graph can be represented via an assignment of a set of integer time-labels to every edge, indicating the discrete time steps when this edge is active. While most of the recent theoretical research on temporal graphs focused on temporal paths and other "path-related" temporal notions, only few attempts have been made to investigate "non-path" temporal problems. In this paper we introduce and study two natural temporal extensions of the classical problem VERTEX COVER. We present a thorough investigation of the computational complexity and approximability of these two temporal covering problems. We provide strong hardness results, complemented by approximation and exact algorithms. Some of our algorithms are polynomial-time, while others are asymptotically almost optimal under the Exponential Time Hypothesis (ETH) and other plausible complexity assumptions. [ABSTRACT FROM AUTHOR]

We combine two fundamental optimization problems related to the construction of phylogenetic trees called maximum rooted triplets consistency and minimally resolved supertree into a new problem, which we call q-maximum rooted triplets consistency (q -MAXRTC). It takes as input a set R of rooted, binary phylogenetic trees with three leaves each and asks for a phylogenetic tree with exactly q internal nodes that contains the largest possible number of trees from R. We prove that q -MAXRTC is NP-hard to approximate within a constant, develop polynomial-time approximation algorithms for different values of q , and show experimentally that representing a phylogenetic tree by one having much fewer nodes typically does not destroy too much branching information. To demonstrate the algorithmic advantage of using trees with few internal nodes, we also propose a new algorithm for computing the rooted triplet distance that is faster than the existing algorithms when restricted to such trees. [ABSTRACT FROM AUTHOR]

Abstract In sum coloring, it is required to find a proper coloring of the vertices of a graph using positive integers, such that the sum of colors of the vertices is minimized. First Fit is the natural coloring algorithm that processes vertices one by one (in some order), and colors the current vertex with the minimum color that was not used for any of its already considered neighbors. Here, we study the approximation ratio of First Fit for sum coloring for the class of claw-free graphs, its most natural subclasses, and its generalizations, and get tight bounds for it. Highlights • A thorough study of the approximation ratio for the natural algorithm First Fit. • A study of sum coloring of graphs, of vertices or edges. • A tight analysis of (k + 1)-claw free graphs, with new types of examples. • A tight analysis for important subclasses of via linear programs. • A tight analysis for edge coloring and a tight analysis for unit interval graphs. [ABSTRACT FROM AUTHOR]

A power assignment is an assignment of transmission power to each of the wireless nodes of a wireless network, so that the induced graph satisfies some desired properties. The cost of a power assignment is the sum of the assigned powers. In this paper, we consider the dual power assignment problem, in which each wireless node is assigned a high- or low-power level, so that the induced graph is strongly connected and the cost of the assignment is minimized. We improve the best known approximation ratio from π 2 6 − 1 36 + ϵ ≈ 1.617 to 11 7 ≈ 1.571 . Moreover, we show that the algorithm of Khuller et al. [11] for the strongly connected spanning subgraph problem, which achieves an approximation ratio of 1.617, is 1.522-approximation algorithm for symmetric directed graphs. The innovation of this paper is in achieving these results by using interesting conditions for the existence of a second Hamiltonian cycle. [ABSTRACT FROM AUTHOR]

The model checking problem of continuous-time Markov chains with respect to continuous-time stochastic logic was introduced and shown to be decidable by Aziz et al. [1,2] in 1996. Unfortunately, their proof is only constructive, but highly unpractical. Later in 2000, an efficient approximate algorithm was proposed by Baier et al. [3,5] for a sublogic with binary until. In this paper, we apply transcendental number theory and classical linear algebra to bridge the gap between the precise but unpractical algorithm, and the imprecise but efficient approximate algorithm. We prove that the approximate algorithm in [3,5] can be used as an off-the-shell tool for a precise model checking algorithm for binary until formulas. Further, we discuss extensions of our results to nested until and continuous-time Markov decision processes. [ABSTRACT FROM AUTHOR]

Let G = ( V , E ) be a unit disk graph corresponding to a given set P of n points in R 2 . We propose a distributed approximation algorithm to find a minimum connected dominating set of G . The maintenance of the connected dominating set constructed is fully localized. Our algorithm produces a connected dominating set of size ( 104 o p t + 52 ) , where o p t is the size of a minimum connected dominating set. The time and message complexities of our algorithm are O ( Δ ) and O ( n ) respectively, where Δ and n are the maximum node degree and number of nodes in G respectively. Our distributed approximation algorithm outperforms existing algorithms in terms of its time and message complexities. We also propose a scheduling scheme that obtains O ( Δ ) conflict-free time slots to deal with interference. [ABSTRACT FROM AUTHOR]

We study the Weighted t -Uniform Sparsest Cut (Weighted t-USC) and other related problems. In an instance of the Weighted t -USC problem, a parameter t and an undirected graph G = ( V , E ) with edge-weights w : E → R ≥ 0 and vertex-weights η : V → R + are given. The goal is to find a vertex set S ⊆ V with | S | ≤ t while minimizing w ( S , V \ S ) / η ( S ) , where w ( S , V \ S ) is the total weight of the edges with exactly one endpoint in S and η ( S ) = ∑ v ∈ S η ( v ) . For this problem, we present a ( O ( log ⁡ t ) , 1 + ϵ ) factor bicriteria approximation algorithm. Our algorithm outperforms the current best algorithm when t = n o ( 1 ) . We also present better approximation algorithms for Weighted ρ -Unbalanced Cut and Min–Max k -Partitioning problems. [ABSTRACT FROM AUTHOR]

We present new results on Boolean matrix factorization and a new algorithm based on these results. The results emphasize the significance of factorizations that provide from-below approximations of the input matrix. While the previously proposed algorithms do not consider the possibly different significance of different matrix entries, our results help measure such significance and suggest where to focus when computing factors. An experimental evaluation of the new algorithm on both synthetic and real data demonstrates its good performance in terms of good coverage by the first few factors as well as a small number of factors needed for an almost exact decomposition and indicates that the algorithm outperforms the available ones in these terms. We also propose future research topics. [ABSTRACT FROM AUTHOR]

Broadcast is a fundamental operation in Wireless Sensor Networks (WSNs) and plays an important role in a communication protocol design. In duty-cycled scenarios, a sensor node can receive a message only in its active time slot, which makes it more difficult to design collision-free scheduling for broadcast operations. Recent studies in this area have focused on minimizing broadcast latency and guaranteeing that all nodes receive a broadcast message. This paper investigates the problem of Minimum Latency Broadcast Scheduling in Duty-Cycled (MLBSDC) WSNs. By using special geometric properties of independent sets of a broadcast tree, we reduce the number of transmissions, consequently reducing the possibility of collision. Allowing multiple transmissions in one working period, our proposed Latency Aware Broadcast Scheduling (LABS) scheme provides a latency-efficient broadcast schedule. Theoretical analysis proves that the scheme has the same approximation ratio and complexity as the previous best algorithm for the MLBSDC problem. Moreover, simulation shows that the new scheme achieves up to 34%, 37%, and 21% performance improvement over previous schemes, in terms of latency, number of transmissions, and energy consumption, respectively. [ABSTRACT FROM AUTHOR]

Abstract: Periodic monitoring is sufficient for sweep coverage with a small number of mobile sensor nodes, whereas a continuous monitoring with static sensor nodes is required for the coverage problem in wireless sensor networks. Finding the minimum number of mobile sensor nodes with a uniform speed to guarantee sweep coverage is NP-hard and it cannot be approximated within a factor of 2 (Li et al., 2011). In this paper we have proposed a 2-approximation algorithm for solving the sweep coverage for a given set of points of interest (PoIs). The best known approximation factor is 3 for this problem (Li et al., 2011). Modification of the algorithm is also proposed for extending lifetime of the mobile sensors, sweep coverage in the presence of obstacles and failure of mobile sensors. When all PoIs are static sensor nodes, we have proposed a distributed approximation algorithm with approximation ratio 2, where the static sensor nodes compute the number of mobile sensor nodes and their positions. We have introduced sweep coverage for a given area of interest (AoI) and proved that the problem is NP-complete. A -approximation algorithm is designed in order to solve the problem for a square region. An improvement over the approximation factor is designed for any rectangular region. Based on our simulation study we have shown that less number mobile sensor nodes are required for our point sweep coverage algorithm compared to the algorithm proposed in Du et al. (2010). [Copyright &y& Elsevier]

Given a collection of multisets { X 1 , X 2 , ... , X k } (k ≥ 2) of positive integers, a multiset S is a common integer partition for them if S is an integer partition of every multiset X i , 1 ≤ i ≤ k. The minimum common integer partition (k -MCIP) problem is defined as to find a CIP for { X 1 , X 2 , ... , X k } with the minimum cardinality. We present a 6 5 -approximation algorithm for the 2-MCIP problem, improving the previous best algorithm of performance ratio 5 4 designed by Chen et al. in 2006. We then extend it to obtain an absolute 0.6 k -approximation algorithm for k -MCIP when k is even (when k is odd, the approximation ratio is 0.6 k + 0.4). [ABSTRACT FROM AUTHOR]

Abstract: A cut-and-paste operation can be a reversal, a transposition, or a transreversal on circular or linear permutations. There are several approximation algorithms for sorting signed permutations by combinations of these operations. For sorting unsigned permutations, we only know an algorithm with performance ratio 3 and its improved version with performance ratio allowing reversals and transpositions. In this paper, we present a 2.25-approximation algorithm for sorting unsigned circular permutations by cut-and-paste operations. A structure called tie is proposed to represent the alternating path of length 5. We can classify the ties into 6 types and find ways to remove the breakpoints for each type of ties, so that every cut-and-paste operation can reduce at least breakpoints averagely. Our algorithm can be used to sort unsigned linear permutations and achieve the performance ratio 2.25 if another operation named revrev is allowed. [Copyright &y& Elsevier]

Abstract: The Malleable Parallel Task Scheduling problem (MPTS) is an extension of one of the most classic scheduling problems (P∥Cmax). The only difference is that for MPTS, each task can be processed simultaneously by more than one processor. Such flexibility could dramatically reduce the makespan, but greatly increase the difficulty for solving the problem. By carefully analyzing some existing algorithms for MPTS, we find each of them suitable for some specific cases, but none is effective enough for all cases. Based on such observations, we introduce some optimization algorithms and improving techniques for MPTS, with their performance analyzed in theory. Combining these optimization algorithms and improving techniques gives rise to our novel scheduling algorithm OCM (Optimizations Combined for MPTS), a 2-approximation algorithm for MPTS. Extensive simulations on random datasets and SPLASH-2 benchmark reveal that for all cases, schedules produced by OCM have smaller makespans, compared with other existing algorithms. [Copyright &y& Elsevier]

Abstract: Given two genomic maps and each represented as a sequence of n gene markers, the maximal strip recovery (MSR) problem is to retain the maximum number of markers in both and such that the resultant subsequences, denoted as and , can be partitioned into the same set of maximal strips, which are common substrings of length greater than or equal to two. The complementary maximal strip recovery (CMSR) problem has the complementary goal to delete the minimum number of markers. Both MSR and CMSR have been shown to be NP-hard and APX-complete, and they admit a 4-approximation and a 3-approximation respectively. In this paper, we present an improved -approximation algorithm for the CMSR problem, with its worst-case performance analysis done through a local amortization with a re-weighting scheme. [Copyright &y& Elsevier]

Abstract: We consider the k-Directed Steiner Forest (k-DSF) problem: Given a directed graph with edge costs, a collection of ordered node pairs, and an integer , find a minimum cost subgraph H of G that contains an st-path for (at least) k pairs . When , we get the Directed Steiner Forest (DSF) problem. The best known approximation ratios for these problems are: for k-DSF by Charikar et al. (1999) , and for DSF by Chekuri et al. (2008) . Our main result is achieving the first sub-linear in terms of approximation ratio for DSF. Specifically, we give an -approximation scheme for DSF. For k-DSF we give a simple greedy -approximation algorithm. This improves upon the best known ratio by Charikar et al. (1999) , and (almost) matches, in terms of k, the best ratio known for the undirected variant (Gupta et al., 2010 ). This algorithm uses a new structure called start-junction tree which may be of independent interest. [Copyright &y& Elsevier]

Abstract: In this paper we propose an approximation algorithm for scheduling malleable tasks with precedence constraints. Based on an interesting model for malleable tasks with continuous processor allotments by Prasanna and Musicus (1991, 1994, 1996) , we define two natural assumptions for malleable tasks: the processing time of any malleable task is non-increasing in the number of processors allotted, and the speedup is concave in the number of processors. We show that under these assumptions the work function of any malleable task is non-decreasing in the number of processors and is convex in the processing time. Furthermore, we propose a two-phase approximation algorithm for the scheduling problem. In the first phase we solve a linear program to obtain a fractional allotment for all tasks. By rounding the fractional solution, each malleable task is assigned a number of processors. In the second phase a variant of the list scheduling algorithm is employed. By choosing appropriate values of the parameters, we show (via a nonlinear program) that the approximation ratio of our algorithm is at most . We also show that our result is asymptotically tight. [Copyright &y& Elsevier]

Abstract: We present a simple randomized algorithmic framework for connected facility location problems. The basic idea is as follows: We run a black-box approximation algorithm for the unconnected facility location problem, randomly sample the clients, and open the facilities serving sampled clients in the approximate solution. Via a novel analytical tool, which we term core detouring, we show that this approach significantly improves over the previously best known approximation ratios for several NP-hard network design problems. For example, we reduce the approximation ratio for the connected facility location problem from 8.55 to 4.00 and for the single-sink rent-or-buy problem from 3.55 to 2.92. The mentioned results can be derandomized at the expense of a slightly worse approximation ratio. The versatility of our framework is demonstrated by devising improved approximation algorithms also for other related problems. [ABSTRACT FROM AUTHOR]