Search

Abstract: Finding the lowest common ancestor (LCA) of two nodes in a binary tree has been focused both in graph theory and computer science. The paper puts forward and proves an analytic criterion for the LCA of two neighboring nodes in a complete binary tree. The criterion mainly concerns addition, subtraction and bitwise operations, needs no searching procedures and thus is easy to implement in software programming as well as hardware programming. An algorithm that has logarithmic time complexity is also presented with C-language implementation in the paper. [Copyright &y& Elsevier]

Abstract: Associative-classification is a promising classification method based on association-rule mining. Significant amount of work has already been dedicated to the process of building a classifier based on association rules. However, relatively small amount of research has been performed in association-rule mining from multi-label data. In such data each example can belong, and thus should be classified, to more than one class. This paper aims at the most demanding, with respect to computational cost, part in associative-classification, which is efficient generation of association rules. This task can be achieved using different frequent pattern mining methods. In this paper, we propose a new method that is based on the state-of-the-art tree-projection-based frequent pattern mining algorithm. This algorithm is modified to improve its efficiency and extended to accommodate the multi-label recurrent-item associative-classification rule generation. The proposed algorithm is tested and compared with A priori-based associative-classification rule generator on two large datasets. [Copyright &y& Elsevier]

Abstract: Katriel and Bodlaender [Irit Katriel, Hans L. Bodlaender, Online topological ordering, ACM Transactions on Algorithms 2 (3) (2006) 364–379] modify the algorithm proposed by Alpern et al. [Bowen Alpern, Roger Hoover, Barry K. Rosen, Peter F. Sweeney, F. Kenneth Zadeck, Incremental evaluation of computational circuits, in: Proceedings of the First Annual ACM–SIAM Symposium on Discrete Algorithms (SODA), 1990, pp. 32–42] for maintaining the topological order of the nodes of a directed acyclic graph while inserting edges and prove that their algorithm runs in time and has an lower bound. In this paper, we give a tight analysis of their algorithm by showing that it runs in time 1 [1] In this paper, we assume that . In fact, our analysis can be easily extended to prove that the algorithm runs in time without the assumption . . [Copyright &y& Elsevier]

Abstract: In this paper we investigate two online scheduling problems. The first one is online scheduling on parallel machines with one machine periodically unavailable. The second problem is online scheduling on two uniform parallel machines where one machine is periodically unavailable. The online paradigm is that jobs arrive over list, i.e., when a job presents, we have to irrevocably assign it before the next one is seen. Preemption is not allowed. The objective is to minimize makespan. We suppose that the length of each available period is normalized to 1 and the length of each unavailable period is . For the first problem, we give an optimal algorithm with competitive ratio 2. For the second problem, we assume that the speed of the periodically unavailable machine is normalized to 1, while the speed of the other one is . In the case where , we design an algorithm and show that it is optimal with competitive ratio . Then we further give some lower bounds on competitive ratio in the case . We also study a special case and prove that algorithm proposed in Xu et al. (2009) is optimal with competitive ratio . [Copyright &y& Elsevier]

Abstract: Numerous privacy-preserving data publishing algorithms were proposed to achieve privacy guarantees such as . Many of them, however, were recently found to be vulnerable to algorithm-based disclosure—i.e., privacy leakage incurred by an adversary who is aware of the privacy-preserving algorithm being used. This paper describes generic techniques for correcting the design of existing privacy-preserving data publishing algorithms to eliminate algorithm-based disclosure. We first show that algorithm-based disclosure is more prevalent and serious than previously studied. Then, we strictly define Algorithm-SAfe Publishing (ASAP) to capture and eliminate threats from algorithm-based disclosure. To correct the problems of existing data publishing algorithms, we propose two generic tools to be integrated in their design: global look-ahead and local look-ahead. To enhance data utility, we propose another generic tool called stratified pick-up. We demonstrate the effectiveness of our tools by applying them to several popular algorithms: Mondrian, Hilb, and MASK. We conduct extensive experiments to demonstrate the effectiveness of our tools in terms of data utility and efficiency. [Copyright &y& Elsevier]

Abstract: The claw finding problem has been studied in terms of query complexity as one of the problems closely connected to cryptography. Given two functions, and , with domain sizes and , respectively, and the same range, the goal of the problem is to find and such that . This problem has been considered in both quantum and classical settings in terms of query complexity. This paper describes an optimal algorithm that uses quantum walk to solve this problem. Our algorithm can be slightly modified to solve the more general problem of finding a tuple consisting of elements in the two function domains that has a prespecified property. It can also be generalized to find a claw of functions for any constant integer , where the domain sizes of the functions may be different. [Copyright &y& Elsevier]

Abstract: A partial function is called a simple function if is the output produced in the leftmost derivation of a word from a nonterminal of a simple context free grammar with output alphabet . In this paper we present an efficient algorithm for testing the equivalence of simple functions. Such functions correspond also to one-state deterministic pushdown transducers. Our algorithm works in time polynomial with respect to , where is the size of the textual description of , and is the maximum of the shortest lengths of words generated by nonterminals of . [Copyright &y& Elsevier]

Abstract: Given a sequence of real numbers and an integer , , the maximum-sum segments problem is to locate the segments whose sums are the largest among all possible segment sums. Recently, Bengtsson and Chen gave an -time algorithm for this problem. Bae and Takaoka later proposed a more efficient algorithm for small . In this paper, we propose an -time algorithm for the same problem, which is superior to both of them when is . We also give the first optimal algorithm for delivering the maximum-sum segments in non-decreasing order if . Then we develop an -time algorithm for the -dimensional version of the problem, where and each dimension, without loss of generality, is of the same size . This improves the best previously known -time algorithm, also by Bengtsson and Chen, where . It should be pointed out that, given a two-dimensional array of size , our algorithm for finding the maximum-sum subarrays is the first one achieving cubic time provided that is . [Copyright &y& Elsevier]

Abstract: Usually, for bin packing problems, we try to minimize the number of bins used or in the case of the dual bin packing problem, maximize the number or total size of accepted items. This paper presents results for the opposite problems, where we would like to maximize the number of bins used or minimize the number or total size of accepted items. We consider off-line and on-line variants of the problems. For the off-line variant, we require that there be an ordering of the bins, so that no item in a later bin fits in an earlier bin. We find the approximation ratios of two natural approximation algorithms, First-Fit-Increasing and First-Fit-Decreasing for the maximum resource variant of classical bin packing. For the on-line variant, we define maximum resource variants of classical and dual bin packing. For dual bin packing, no on-line algorithm is competitive. For classical bin packing, we find the competitive ratio of various natural algorithms. We study the general versions of the problems as well as the parameterized versions where there is an upper bound of on the item sizes, for some integer k. [Copyright &y& Elsevier]