Search

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]

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]

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]

We investigate the existence of approximation algorithms for maximization of submodular functions, that run in a fixed parameter tractable (FPT) time. Given a non-decreasing submodular set function v : 2 X → R the goal is to select a subset S of K elements from X such that v ( S ) is maximized. We identify three properties of set functions, referred to as p -separability properties, and we argue that many real-life problems can be expressed as maximization of submodular, p -separable functions, with low values of the parameter p . We present FPT approximation schemes for the minimization and maximization variants of the problem, for several parameters that depend on characteristics of the optimized set function, such as p and K . [ABSTRACT FROM AUTHOR]

We consider the problem of scheduling a set of jobs, each one specified by its release date, its deadline and its processing volume, on a set of heterogeneous speed-scalable processors, where the energy-consumption rate is processor-dependent. Our objective is to minimize the total energy consumption when both the preemption and the migration of jobs are allowed. We propose a new algorithm based on a compact linear programming formulation. Our method approaches the value of the optimal solution within any desired accuracy for a large set of continuous power functions. Furthermore, we develop a faster combinatorial algorithm based on flows for standard power functions and jobs whose density is lower bounded by a small constant. Finally, we extend and analyze the AVerage Rate (AVR) online algorithm in the heterogeneous setting. [ABSTRACT FROM AUTHOR]

Given an edge-weighted connected graph G on n vertices and a positive integer k ≤ n , a subgraph of G on k vertices is called a k -subgraph in G . We design combinatorial approximation algorithms for finding a connected k -subgraph in G such that its weighted density is at least a factor Ω ( max ⁡ { 1 / k , k 2 / n 2 } ) of the maximum weighted density among all k -subgraph in G (which are not necessarily connected), where max ⁡ { 1 / k , k 2 / n 2 } ≥ n − 2 / 3 implies an O ( n 2 / 3 ) -approximation ratio. We obtain improved O ( n 2 / 5 ) -approximation for unit weights. These particularly provide the first non-trivial approximations for the heaviest/densest connected k -subgraph problem on general graphs. We also give O ( n log ⁡ n ) -approximation for the problem on general weighted interval graphs. [ABSTRACT FROM AUTHOR]

Deadlock detection in concurrent programs that create networks with arbitrary numbers of nodes is extremely complex and solutions either give imprecise answers or do not scale. To enable the analysis of such programs, (1) we define an algorithm for detecting deadlocks of a basic model featuring recursion and fresh name generation: the lam programs , and (2) we design a type system for value-passing CCS that returns lam programs. We show the soundness of the type system, and develop a type inference algorithm for it. The resulting algorithm is able to check deadlock-freedom of programs that cannot be handled by previous analyses, such as those that build unbounded networks. [ABSTRACT FROM AUTHOR]

The maximum internal spanning tree problem asks for a spanning tree of a given graph that has the maximum number of internal vertices among all spanning trees of this graph. In its parameterized version, we are interested in whether the graph has a spanning tree with at least k internal vertices. Fomin et al. (2013) [4] crafted a very ingenious reduction rule, and showed that a simple application of this rule is sufficient to yield a 3 k -vertex kernel, implying an O ⁎ ( 8 k ) -time parameterized algorithm. Using depth-2 local search, Knauer and Spoerhase (2015) [9] developed a (5/3)-approximation algorithm for the optimization version. We try deeper local search: We conduct a thorough combinatorial analysis on the obtained spanning trees and explore their algorithmic consequences. We first observe that from the spanning tree obtained by depth-3 local search, one can easily find a reducible structure and apply the reduction rule of Fomin et al. This gives an improved kernel of 2 k vertices, and as a by-product, a deterministic algorithm running in time O ⁎ ( 4 k ) . We then go even deeper by considering the spanning tree obtained by depth-5 local search. It is shown that the number of internal vertices of this spanning tree is at least 2/3 of the maximum number a spanning tree can have, thereby delivering an improved approximation algorithm with ratio 1.5 for the problem. [ABSTRACT FROM AUTHOR]

Herein, we present Linear Threshold Ranking (LTR), an extension of the Linear Threshold Model (Kempe et al., KDD 2003). LTR models the spread of a message supporting a target candidate in a social network and how social influence affects the preferences of the voters who receive it, in elections based on positional scoring rules. The problem of election control through social influence requires finding a bounded subset of nodes to be the initial spreaders of this message to maximize the Margin of Victory of a target candidate against the most voted opponent. We prove the problem is NP -hard in LTR. By showing the equivalence of LTR with alternative stochastic processes and then exploiting submodularity, we provide a 1 3 (1 − 1 e) approximation algorithm. We achieve similar results also in the destructive variation of LTR, where the message undermines a target candidate, negatively influencing the voters' preference on that candidate. [ABSTRACT FROM AUTHOR]

In this paper we establish an algorithmic framework between bin packing and strip packing, with which strip packing can be very well approximated by applying some bin packing algorithms. More precisely we obtain the following results: (1) Any off-line bin packing algorithm can be applied to strip packing maintaining almost the same asymptotic worst-case ratio. (2) A class of Harmonic-based algorithms for bin packing, such as Refined Harmonic, Modified Harmonic, Harmonic++, can be applied to online strip packing. In particular, we show that online strip packing admits an upper bound of 1.58889 + ϵ on the asymptotic competitive ratio, for any arbitrarily small ϵ > 0 . This significantly improves the previously best bound of 1.6910 and affirmatively answers an open question posed by Csirik and Woeginger (1997). Moreover, the time complexity mainly depends on a sorting procedure and the bin packing algorithms employed. [ABSTRACT FROM AUTHOR]

Anonymity protocols focus on protecting the identities of senders and/or receivers in a network communication. Most of these protocols rely on randomness to achieve their goal and therefore can very well be represented as noisy channels in the information theoretic sense. In this paper we examine the problem of measuring the anonymity degree of anonymity protocols. We investigate a new idea of measuring anonymity based on how much the rows of the channel probabilities matrix are different from each other. We propose a new and generic approximation algorithm for the open problem of finding where anonymity of a given protocol is minimized. We illustrate how the probabilities matrix is constructed for some known anonymity protocols and we use the information leakage measures to study known attacks on those protocols. The analysis shows counter intuitive results in particular for Timed dynamic pool (Cottrell) mixes. Finally, we discuss the applicability of the proposed measures on Tor Network. [ABSTRACT FROM AUTHOR]

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]

In the generalized budgeted submodular set function maximization problem, we are given a ground set of elements and a set of bins. Each bin has its own cost and the cost of each element depends on its associated bin. The goal is to find a subset of elements along with an associated set of bins such that the overall costs of both is at most a given budget, and the profit is maximized. We present an algorithm that guarantees a 1 2 (1 − 1 e α ) -approximation, where α ≤ 1 is the approximation factor of an algorithm for a sub-problem. If the costs satisfy a specific condition, we provide a polynomial-time algorithm that gives us α = 1 − ϵ , while for the general case we design an algorithm with α = 1 − 1 e − ϵ. We extend our results providing a bi-criterion approximation algorithm where we can spend an extra budget up to a factor β ≥ 1 to guarantee a 1 2 (1 − 1 e α β ) -approximation. [ABSTRACT FROM AUTHOR]

Abstract: Node-Weighted Steiner Forest is the following problem: Given an undirected graph, a set of pairs of terminal vertices, a weight function on the vertices, find a minimum weight set of vertices that includes and connects each pair of terminals. We consider the restriction to planar graphs where the problem remains NP-complete. Demaine et al. showed that the generic primal-dual algorithm of Goemans and Williamson is a 6-approximation on planar graphs. We present (1) two different analyses to prove an approximation factor of 3, (2) show that our analysis is best possible for the chosen proof strategy, and (3) generalize this result to feedback problems on planar graphs. We give a simple proof for the first result using contraction techniques and following a standard proof strategy for the generic primal-dual algorithm. Given this proof strategy our analysis is best possible which implies that proving a better upper bound for this algorithm, if possible, would require different proof methods. Then, we give a reduction on planar graphs of Feedback Vertex Set to Node-Weighted Steiner Tree, and Subset Feedback Vertex Set to Node-Weighted Steiner Forest. This generalizes our result to the feedback problems studied by Goemans and Williamson. For the opposite direction, we show how our constructions can be combined with the proof idea for the feedback problems to yield an alternative proof of the same approximation guarantee for Node-Weighted Steiner Forest. [Copyright &y& Elsevier]

Abstract: We present a deterministic black box solution for online approximate matching. Given a pattern of length m and a streaming text of length n that arrives one character at a time, the task is to report the distance between the pattern and a sliding window of the text as soon as the new character arrives. Our solution requires time for each input character, where is the total running time of the best offline algorithm. The types of approximation that are supported include exact matching with wildcards, matching under the Hamming norm, approximating the Hamming norm, k-mismatch and numerical measures such as the and norms. For these examples, the resulting online algorithms take , , , , and time per character, respectively. The space overhead is linear in the pattern size, which we show is optimal for any deterministic algorithm. [Copyright &y& Elsevier]

Abstract: For more and more applications, it is important to be able to compute the treewidth of a given graph and to find tree decompositions of small width reasonably fast. This paper gives an overview of several upper bound heuristics that have been proposed and tested for the problem of determining the treewidth of a graph and finding tree decompositions. Each of the heuristics produces tree decompositions whose width may be larger than the optimal width. However, experiments show that in many cases, the heuristics give tree decompositions whose width is close to the exact treewidth of the input graphs. [Copyright &y& Elsevier]

Abstract: In this paper, we consider the problem of covering a set of strings S with a set C of substrings in S, where C is said to cover S if every string in S can be written as a concatenation of the substrings in C. We discuss applications for the problem that arise in the context of computational biology and formal language theory. We then proceed to show several hardness of approximation results for the problem, and in the main part of the paper, we focus on devising approximation algorithms using two generic paradigms—the local-ratio technique and linear programming rounding. [Copyright &y& Elsevier]

Abstract: We study the problem of scheduling transmissions on the downlink of IEEE 802.16/WiMAX systems that use the OFDMA technology. These transmissions are scheduled using a matrix whose dimensions are frequency and time, where every matrix cell is a time slot on some carrier channel. The IEEE 802.16 standard mandates that: (i) every transmission occupies a rectangular set of cells, and (ii) transmissions must be scheduled according to a given order. We show that if the number of cells required by a transmission is not limited (up to the matrix size), the problem of maximizing matrix utilization is very hard to approximate. On the positive side we show that if the number of cells of every transmission is limited to some constant fraction of the matrix area, the problem can be approximated to within a constant factor. As far as we know this is the first paper that considers this sequential rectangle placement problem. [Copyright &y& Elsevier]

Abstract: We propose a new approximation technique for Hybrid Automata. Given any Hybrid Automaton H, we call Approx(H, k) the Polynomial Hybrid Automaton obtained by approximating each formula ϕ in H with the formulae ϕ k obtained by replacing the functions in ϕ with their Taylor polynomial of degree k. We prove that Approx(H, k) is an over-approximation of H. We study the conditions ensuring that, given any ϵ >0, some k 0 exists such that, for all k > k 0, the “distance” between any vector satisfying ϕ k and at least one vector satisfying ϕ is less than ϵ. We study also conditions ensuring that, given any ϵ >0, some k 0 exists such that, for all k > k 0, the “distance” between any configuration reached by Approx(H, k) in n steps and at least one configuration reached by H in n steps is less than ϵ. [Copyright &y& Elsevier]

Abstract: We study integrated prefetching and caching in single and parallel disk systems. In the first part of the paper we investigate approximation algorithms for the single disk problem. There exist two very popular approximation algorithms called Aggressive and Conservative for minimizing the total elapsed time. We give a refined analysis of the Aggressive algorithm, improving the original analysis by Cao et al. We prove that our new bound is tight. Additionally we present a new family of prefetching and caching strategies and give algorithms that perform better than Aggressive and Conservative. In the second part of the paper we investigate the problem of minimizing stall time in parallel disk systems. We present a polynomial time algorithm for computing a prefetching/caching schedule whose stall time is bounded by that of an optimal solution. The schedule uses at most extra memory locations in cache. This is the first polynomial time algorithm that, using a small amount of extra resources, computes schedules whose stall times are bounded by that of optimal schedules not using extra resources. Our algorithm is based on the linear programming approach of [Journal of the ACM, 47 (2000) 969]. However, in order to achieve minimum stall times, we introduce the new concept of synchronized schedules in which fetches on the disks are performed completely in parallel. [Copyright &y& Elsevier]

We introduce a new class of scheduling problems in which the optimization is performed by the worker (single “machine”) who performs the tasks. A typical worker’s objective is to minimize the amount of work he does (he is “lazy”), or more generally, to schedule as inefficiently (in some sense) as possible. The worker is subject to the constraint that he must be busy when there is work that he can do; we make this notion precise both in the preemptive and nonpreemptive settings. The resulting class of “perverse” scheduling problems, which we denote “Lazy Bureaucrat Problems,” gives rise to a rich set of new questions that explore the distinction between maximization and minimization in computing optimal schedules. [Copyright &y& Elsevier]

Scheduling jobs with pairwise conflicts is modeled by the graph multicoloring problem. It occurs in two versions: in the preemptive case, each vertex may get any set of colors, while in the non-preemptive case, the set of colors assigned to each vertex has to be contiguous. We study these versions of the multicoloring problem on trees, under the sum-of-completion-times objective. In particular, we give a quadratic algorithm for the non-preemptive case, and a faster algorithm in the case that all job lengths are short, while we present a polynomial-time approximation scheme for the preemptive case. [Copyright &y& Elsevier]

The Min Label s - t Cut problem is a fundamental problem in combinatorial optimization. This problem comes from many applications in real world, for example, information security and computer networks. We study two linear programs for Min Label s - t Cut , proving that both of them have large integrality gaps, namely, Ω (m) and Ω (m 1 / 3 − ϵ) for the respective linear programs, where m is the number of edges in the input graph of the problem and ϵ > 0 is any arbitrarily small constant. As Min Label s - t Cut is NP-hard and the linear programming technique is a main approach to design approximation algorithms, our results give negative answer to the hope that designs can be found for better approximation algorithms for Min Label s - t Cut that purely rely on linear programming. [ABSTRACT FROM AUTHOR]

Line of Sight (LoS) networks were designed to model wireless communication in settings which may contain obstacles. For fixed positive integer d , and positive integer ω , a graph G = (V , E) is a (d -dimensional) LoS network with range parameter ω if it can be embedded in a finite cube of the d -dimensional integer grid so that each pair of vertices in V are adjacent if and only if their embedding coordinates differ only in one position and such difference is less than ω. In this paper we investigate a dynamic programming (DP) approach which can be used to obtain efficient algorithmic solutions for various combinatorial problems in LoS networks. In particular DP solves the Maximum Independent Set (MIS) problem in LoS networks optimally, for any ω , on narrow LoS networks (i.e. networks which can be embedded in a k × k ... × k × n region, for some fixed k independent of n). In the unrestricted case it has been shown that the (decision version of the) problem is NP-hard when 2 < ω = O (n 1 − δ) , for fixed 0 < δ < 1. We describe how DP can be used as a building block in the design of good approximation algorithms in this case. In particular we present a semi-online polynomial-time approximation scheme for the MIS problem in narrow d -dimensional LoS networks, as well as a polynomial-time 2-approximation algorithm and a fast polynomial time approximation scheme for the MIS problem in arbitrary d -dimensional LoS networks. Finally we comment on how the approach can be adapted to prove similar results for a number of important optimization problems in LoS networks. [ABSTRACT FROM AUTHOR]