Approximation algorithm for hotlink assignment in the greedy model

Link-based information structures such as the web can be enhanced through the addition of hotlinks. Assume that each node in the information structure is associated with a weight representing the access frequency of the node by users. In order to access a particular node, the user must follow a path leading to it from the root. By adding new hotlinks to the tree, it may be possible to reduce the access cost of the system, namely, the expected number of steps needed to reach a leaf from the root, assuming the user can decide which hotlinks to follow in each step. The hotlink assignment   problem involves finding a set of hotlinks (with at most K=O(1)$K=O\left(1\right)$ hotlinks emanating from every node) maximizing the gain in the expected cost. The paper addresses this problem in two user models, namely, the traditional clairvoyant user model employed in [P. Bose, J. Czyzowicz, L. Gasieniec, E. Kranakis, D. Krizanc, A. Pelc, M.V. Martin, Strategies for hotlink assignments, in: Proc. 11th Symp. on Algorithms and Computation, 2000, pp. 23–34; E. Kranakis, D. Krizanc, S. Shende, Approximating hotlink assignments, in: Proc. 12th Symp. on Algorithms and Computation, 2001, pp. 756–767; P. Bose, D. Krizanc, S. Langerman, P. Morin, Asymmetrical communication protocols via hotlink assignments, in: Proc. 9th Colloq. on Structural Information and Communication Complexity, 2002, pp. 33–39; R. Matichin, D. Peleg, Approximation algorithm for hotlink assignments in web directories, in: Proc. Workshop on Algorithms and Data Structures, 2003, pp. 271–280] and the more realistic greedy user model recently introduced in [O. Gerstel, S. Kutten, R. Matichin, D. Peleg, Hotlink enhancement algorithms for web directories, in: Proc. 14th Symp. on Algorithms and Computation, 2003, pp. 68–77], and presents a polynomial time 2-approximation algorithm for the hotlink assignment problem on rooted directed trees.     

Near-Entropy Hotlink Assignments

Consider a rooted tree T of arbitrary maximum degree d representing a collection of n web pages connected via a set of links, all reachable from a source home page represented by the root of T. Each web page i carries a probability p _i representative of the frequency with which it is visited. By adding hotlinks—shortcuts from a node to one of its descendents—we wish to minimize the expected number of steps l needed to visit pages from the home page, expressed as a function of the entropy H(p) of the access probabilities p. This paper introduces several new strategies for effectively assigning hotlinks in a tree. For assigning exactly one hotlink per node, our method guarantees an upper bound on l of 1.141H(p)+1 if d>2 and 1.08H(p)+2/3 if d=2. We also present the first efficient general methods for assigning at most k hotlinks per node in trees of arbitrary maximum degree, achieving bounds on l of at most \frac2H(p)log(k+1)+1\frac{2H(p)}{\log(k+1)}+1 and \fracH(p)log(k+d)-logd+1\frac{H(p)}{\log(k+d)-\log d}+1 , respectively. All our methods are strong, i.e., they provide the same guarantees on all subtrees after the assignment. We also present an algorithm implementing these methods in O(nlog n) time, an improvement over the previous O(n ²) time algorithms. Finally we prove a Ω(nlog n) lower bound on the running time of any strong method that guarantee an average access time strictly better than 2H(p).     

Dynamic Hotlinks

Consider a directed rooted tree T=(V,E) representing a collection V of n web pages connected via a set E of links all reachable from a source home page, represented by the root of T. Each web page i carries a weight w _i representative of the frequency with which it is visited. By adding hotlinks, shortcuts from a node to one of its descendants, we are interested in minimizing the expected number of steps needed to visit pages from the home page. We give the first linear time algorithm for assigning hotlinks so that the number of steps to access a page i from the root of the tree reaches the entropy bound, i.e. is at most O(log (W/w _i )) where W=∑ _i∈T w _i . The best previously known algorithm for this task runs in time O(n ²). We also give the first efficient data structure for maintaining hotlinks when nodes are added, deleted or their weights modified, in amortized time O(log (W/w _i )) per update. The data structure can be made adaptive, i.e. reaches the entropy bound in the amortized sense without knowing the weights w _i in advance.     

Approximate hotlink assignment

Consider a directed rooted tree T=(V,E) of maximal degree d representing a collection V of web pages connected via a set E of links all reachable from a source home page, represented by the root of T. Each leaf web page carries a weight representative of the frequency with which it is visited. By adding hotlinks, shortcuts from a node to one of its descendents, we are interested in minimizing the expected number of steps needed to visit the leaf pages from the home page. We give an O(N²) time algorithm for assigning hotlinks so that the expected number of steps to reach the leaves from the root of the tree is at most H(p)/(log(d+1)−(d/(d+1))logd)+(d+1)/d, where H(p) is the entropy of the probability (frequency) distribution p=〈p₁,p₂,…,p_N〉 on the N leaves of the given tree, i.e., p_i is the weight on the ith leaf. The best known lower bound for this problem is H(p)/log(d+1). We also show how to adapt our algorithm to complete trees of a given degree d and in this case we prove it is optimal, asymptotically in d.     

A linear time algorithm for computing a most reliable source on a tree network with faulty nodes

Given an unreliable communication network, we seek for a node which maximizes the expected number of nodes that are reachable from it. Such a node is called a most reliable source (MRS) of the network. In communication networks, failures may occur to both links and nodes. Previous studies have considered the case where each link has an independent operational probability, while the nodes are immune to failures. In practice, however, failures may happen to the nodes as well, including both transmitting fault and receiving fault. Recently, another variant of the MRS problem is studied, where all links are immune to failures and each node has an independent transmitting probability and receiving probability, and an O(n²) time algorithm is presented for computing an MRS on tree networks with n nodes. In this paper, we present a faster algorithm for this problem, with a time complexity of O(n).     

Improving a fixed parameter tractability time bound for the shadow problem

Consider a forest of k trees and n nodes together with a (partial) function σ mapping leaves of the trees to non-root nodes of other trees. Define the shadow of a leaf ? to be the subtree rooted at σ(?). The shadow problem asks whether there is a set S of leaves exactly one from each tree such that none of these leaves lies in the shadow of another leaf in S. This graph theoretical problem as shown in Franco et al. (Discrete Appl. Math. 96 (1999) 89) is equivalent to the falsifiability problem for pure implicational Boolean formulas over n variables with k occurences of the constant false as introduced in: Heusch J. Wiedermann, P. Hajek (Eds.), Proceedings of the Twentieth International Symposium on Mathematical Foundations of Computer Science (MFCS’95), Prague, Czech Republic, Lecture Notes in Computer Science, Vol. 969, Springer, Berlin, 1995, pp. 221-226, where its NP-completeness is shown for arbitrary values of k and a time bound of O(n^k) for fixed k was obtained. In Franco et al. (1999) this bound is improved to O(n²k^k) showing the problem's fixed parameter tractability (Congr. Numer. 87 (1992) 161). In this paper the bound O(n³3^k) is achieved by dynamic programming techniques thus significantly improving the fixed parameter part.     

Computing Optimal Steiner Trees in Polynomial Space

Given an n-node edge-weighted graph and a subset of k terminal nodes, the NP-hard (weighted) Steiner tree problem is to compute a minimum-weight tree which spans the terminals. All the known algorithms for this problem which improve on trivial O(1.62 ⁿ )-time enumeration are based on dynamic programming, and require exponential space. Motivated by the fact that exponential-space algorithms are typically impractical, in this paper we address the problem of designing faster polynomial-space algorithms. Our first contribution is a simple O((27/4) ^k n ^O(logk))-time polynomial-space algorithm for the problem. This algorithm is based on a variant of the classical tree-separator theorem: every Steiner tree has a node whose removal partitions the tree in two forests, containing at most 2k/3 terminals each. Exploiting separators of logarithmic size which evenly partition the terminals, we are able to reduce the running time to $O(4^{k}n^{O(\log^{2} k)})$ . This improves on trivial enumeration for roughly k<n/3, which covers most of the cases of practical interest. Combining the latter algorithm (for small k) with trivial enumeration (for large k) we obtain a O(1.59 ⁿ )-time polynomial-space algorithm for the weighted Steiner tree problem. As a second contribution of this paper, we present a O(1.55 ⁿ )-time polynomial-space algorithm for the cardinality version of the problem, where all edge weights are one. This result is based on a improved branching strategy. The refined branching is based on a charging mechanism which shows that, for large values of k, convenient local configurations of terminals and non-terminals exist. The analysis of the algorithm relies on the Measure & Conquer approach: the non-standard measure used here is a linear combination of the number of nodes and number of non-terminals. Using a recent result in Nederlof (International colloquium on automata, languages and programming (ICALP), pp. 713–725, 2009), the running time can be reduced to O(1.36 ⁿ ). The previous best algorithm for the cardinality case runs in O(1.42 ⁿ ) time and exponential space.     

A polynomial algorithm for the multiple knapsack problem with divisible item sizes

A polynomial algorithm for the multiple bounded knapsack problem with divisible item sizes is presented. The complexity of the algorithm is O(n²+nm), where n and m are the number of different item sizes and knapsacks, respectively. It is also shown that the algorithm complexity reduces to O(nlogn+nm) when a single copy exists of each item.     

An optimal algorithm for the maximum-density path in a tree

We studied the problem of finding the maximum-density path in a tree. By spine decomposition and a linear-time algorithm for the maximum density segment problem, we developed an O(nlogn) time algorithm, which improves the previously best result of O(nlog²n) by using centroid decomposition. We also show the time complexity is optimal in the algebraic computation tree model.     

Using spine decompositions to efficiently solve the length-constrained heaviest path problem for trees

The length-constrained heaviest path (LCHP) in a weighted tree T, where each edge is assigned a weight and a length, is the path P in T with maximum total path weight and total path length bounded by a given value B. This paper presents an O(nlogn) time LCHP algorithm which utilizes a data structure constructed from the spine decomposition of the input tree. This is an improvement over the existing algorithm by Wu et al. (1999), which runs in O(nlog²n) time. Our method also improves on a previous O(nlogn) time algorithm by Kim (2005) for the special case of finding a longest nonnegative path in a constant degree tree in that we can handle trees of arbitrary degree within the same time bounds.     

Index-based query processing on distributed multidimensional data

This work introduces decentralized query processing techniques based on MIDAS, a novel distributed multidimensional index. In particular, MIDAS implements a distributed k-d tree, where leaves correspond to peers, and internal nodes dictate message routing. MIDAS requires that peers maintain little network information, and features mechanisms that support fault tolerance and load balancing. The proposed algorithms process point and range queries over the multidimensional indexed space in only O(log n) hops in expectance, where n is the network size. For nearest neighbor queries, two processing alternatives are discussed. The first, termed eager processing, has low latency (expected value of O(log n) hops) but may involve a large number of peers. The second, termed iterative processing, has higher latency (expected value of O(log² n) hops) but involves far fewer peers. A detailed experimental evaluation demonstrates that our query processing techniques outperform existing methods for settings involving real spatial data as well as in the case of high dimensional synthetic data.     

An Approximation Algorithm for Binary Searching in Trees

We consider the problem of computing efficient strategies for searching in trees. As a generalization of the classical binary search for ordered lists, suppose one wishes to find a (unknown) specific node of a tree by asking queries to its arcs, where each query indicates the endpoint closer to the desired node. Given the likelihood of each node being the one searched, the objective is to compute a search strategy that minimizes the expected number of queries. Practical applications of this problem include file system synchronization and software testing. Here we present a linear time algorithm which is the first constant factor approximation for this problem. This represents a significant improvement over previous O(log n)-approximation.     

Fast heuristic algorithms for rectilinear steiner trees

A fundamental problem in circuit design is how to connectn points in the plane, to make them electrically common using the least amount of wire. The tree formed, a Steiner tree, is usually constructed with respect to the rectilinear metric. The problem is known to be NP-complete; an extensive review of proposed heuristics is given. An early algorithm by Hanan is shown to have anO(n logn) time implementation using computational geometry techniques. The algorithm can be modified to do sequential searching inO(n ²) total time. However, it is shown that the latter approach runs inO(n ^3/2) expected time, forn points selected from anm×m grid. Empirical results are presented for problems up to 10,000 points.     

Self-stabilizing minimum degree spanning tree within one from the optimal degree

We propose a self-stabilizing algorithm for constructing a Minimum Degree Spanning Tree (MDST) in undirected networks. Starting from an arbitrary state, our algorithm is guaranteed to converge to a legitimate state describing a spanning tree whose maximum node degree is at most Δ^∗+1, where Δ^∗ is the minimum possible maximum degree of a spanning tree of the network.To the best of our knowledge, our algorithm is the first self-stabilizing solution for the construction of a minimum degree spanning tree in undirected graphs. The algorithm uses only local communications (nodes interact only with the neighbors at one hop distance). Moreover, the algorithm is designed to work in any asynchronous message passing network with reliable FIFO channels. Additionally, we use a fine grained atomicity model (i.e., the send/receive atomicity). The time complexity of our solution is O(mn²logn) where m is the number of edges and n is the number of nodes. The memory complexity is O(δlogn) in the send-receive atomicity model (δ is the maximal degree of the network).     

An efficient certifying algorithm for the Hamiltonian cycle problem on circular-arc graphs

A certifying algorithm for a problem is an algorithm that provides a certificate with each answer that it produces. The certificate is an evidence that can be used to authenticate the correctness of the answer. A Hamiltonian cycle in a graph is a simple cycle in which each vertex of the graph appears exactly once. The Hamiltonian cycle problem is to determine whether or not a graph contains a Hamiltonian cycle. The best result for the Hamiltonian cycle problem on circular-arc graphs is an O(n²logn)-time algorithm, where n is the number of vertices of the input graph. In fact, the O(n²logn)-time algorithm can be modified as a certifying algorithm although it was published before the term certifying algorithms appeared in the literature. However, whether there exists an algorithm whose time complexity is better than O(n²logn) for solving the Hamiltonian cycle problem on circular-arc graphs has been opened for two decades. In this paper, we present an O(Δn)-time certifying algorithm to solve this problem, where Δ represents the maximum degree of the input graph. The certificates provided by our algorithm can be authenticated in O(n) time.     

Polynomial-time primal simplex algorithms for the minimum cost network flow problem

We present two variants of the primal network simplex algorithm which solve the minimum cost network flow problem in at mostO(n ² logn) pivots. Here we define the network simplex method as a method which proceeds from basis tree to adjacent basis tree regardless of the change in objective function value; i.e., the objective function is allowed to increase on some iterations. The first method is an extension of theminimum mean augmenting cycle-canceling method of Goldberg and Tarjan. The second method is a combination of a cost-scaling technique and a primal network simplex method for the maximum flow problem. We also show that the diameter of the primal network flow polytope is at mostn ² m.     

Testing Convexity Properties of Tree Colorings

A coloring of a graph is convex if it induces a partition of the vertices into connected subgraphs. Besides being an interesting property from a theoretical point of view, tests for convexity have applications in various areas involving large graphs. We study the important subcase of testing for convexity in trees. This problem is linked, among other possible applications, with the study of phylogenetic trees, which are central in genetic research, and are used in linguistics and other areas. We give a 1-sided, non-adaptive, distribution-free ε-test for the convexity of tree colorings. The query complexity of our test is O(k/ε), where k is the number of colors, and the additional computational complexity is O(n). On the other hand, we prove a lower bound of \(\Omega(\sqrt{k/\epsilon})\) on the query complexity of tests for convexity in the standard model, which applies even for (unweighted) paths. We also consider whether the dependency on k can be reduced in some cases, and provide an alternative testing algorithm for the case of paths. Then we investigate a variant of convexity, namely quasi-convexity, in which all but one of the colors are required to induce connected components. For this problem we provide a 1-sided, non-adaptive ε-test with query complexity O(k/ε ²) and time complexity O(kn/ε). For both our convexity and quasi-convexity tests, we show that, assuming that a query takes constant time, the time complexity can be reduced to a constant independent of n if we allow a preprocessing stage of time O(n) and O(n ²), respectively. Finally, we show how to test for a variation of convexity and quasi-convexity where the maximum number of connectivity classes of each color is allowed to be a constant value other than 1.     

A refined search tree technique for Dominating Set on planar graphs

We establish a refined search tree technique for the parameterized DOMINATING SET problem on planar graphs. Here, we are given an undirected graph and we ask for a set of at most k vertices such that every other vertex has at least one neighbor in this set. We describe algorithms with running times O(8^kn) and O(8^kk+n³), where n is the number of vertices in the graph, based on bounded search trees. We describe a set of polynomial time data-reduction rules for a more general “annotated” problem on black/white graphs that asks for a set of k vertices (black or white) that dominate all the black vertices. An intricate argument based on the Euler formula then establishes an efficient branching strategy for reduced inputs to this problem. In addition, we give a family examples showing that the bound of the branching theorem is optimal with respect to our reduction rules. Our final search tree algorithm is easy to implement; its analysis, however, is involved.     

Reconstructing a Binary Tree from Its Traversals in Doubly Logarithmic CREW Time

We consider the following problem. For a binary tree T = (V, E) where V = {1, 2, ..., n}, given its inorder traversal and either its preorder or its postorder traversal, reconstruct the binary tree. We present a new parallel algorithm for this problem. Our algorithm requires O(n) space. The main idea of our algorithm is to reduce the reconstruction process to merging two sorted sequences. With the best parallel merging algorithms, our algorithm can be implemented in O(log log n) time using O(n/log log n) processors on the CREW PRAM (or in O(log n) time using O(n/log n) processors on the EREW PRAM). Our result provides one more example of a fundamental problem which can be solved by optimal parallel algorithms in O(log log n)time on the CREW PRAM.     

Algorithms for updating minimal spanning trees

The problem of finding the minimal spanning tree on an undirected weighted graph has been investigated by many people and O(n²) algorithms are well known. P. M. Spira and A. Pan (Siam J. Computing4 (1975), 375–380) present an O(n) algorithm for updating the minimal spanning tree if a new vertex is inserted into the graph. In this paper, we present another O(n) algorithm simpler than that presented by Spira and Pan for the insertion of a vertex. Spira and Pan further show that the deletion of a vertex requires O(n²) steps. If all the vertices are considered, O(n³) steps may be used. The algorithm which we present here takes only O(n²) steps and labels the vertices of the graph in such a way that any vertex may be deleted from the graph and the minimal spanning tree can be updated in constant time. Similar results are obtained for the insertion and the deletion of an edge.