Search

This paper studies the average complexity on the number of comparisons for sorting algorithms. Its information-theoretic lower bound is n lg ⁡ n − 1.4427 n + O (log ⁡ n). For many efficient algorithms, the first n lg ⁡ n term is easy to achieve and our focus is on the (negative) constant factor of the linear term. The current best value is −1.3999 for the MergeInsertion sort. Our new value is −1.4106, narrowing the gap by some 25%. An important building block of our algorithm is "two-element insertion," which inserts two elements A and B , A < B , into a sorted sequence T. This insertion algorithm is still sufficiently simple for rigorous mathematical analysis and works well for a certain range of the length of T for which the simple binary insertion does not, thus allowing us to take a complementary approach together with the binary insertion. [ABSTRACT FROM AUTHOR]

In this paper, we introduce obnoxious effects into obnoxious facility location games on a line, where each agent i has a private location x i on a closed interval [ 0 , 1 ] and one facility will be built on a location y in the interval according to the bids of all the agents. In addition, there are two thresholds d 1 and d 2 in the utility function of each agent, where 0 ≤ d 1 ≤ d 2 ≤ 1 . Denote d ( y , x i ) = | y − x i | to be the distance between agent i and the facility on the location y . The utility function of agent i is 0 if d ( y , x i ) is at most d 1 ; 1 if d ( y , x i ) is at least d 2 ; otherwise a linear increasing function between 0 and 1. Each agent attempts to get the largest utility while the social welfare is to maximize the sum of all the agents' utilities. The classic obnoxious facility game [4,11] is a special case of our problem when d 1 = 0 and d 2 = 1 . In this work, we first study the hardness of approximate mechanism design on this generalized problem, which states that our problem cannot admit any deterministic strategy-proof mechanism with bounded approximation ratio if d 1 ≥ 1 2 . Then we limit the thresholds to some ranges, both deterministic and randomized strategy-proof mechanisms are studied, and the approximation ratios vary with the specific values of d 1 and d 2 . [ABSTRACT FROM AUTHOR]

The Lyndon factorization of a string w is a unique factorization ℓ 1 p 1 , … , ℓ m p m of w such that ℓ 1 , … , ℓ m is a sequence of Lyndon words that is monotonically decreasing in lexicographic order. In this paper, we consider the reverse-engineering problem on Lyndon factorization : Given a sequence S = ( ( s 1 , p 1 ) , … , ( s m , p m ) ) of ordered pairs of positive integers, find a string w whose Lyndon factorization corresponds to the input sequence S , i.e., the Lyndon factorization of w is in a form of ℓ 1 p 1 , … , ℓ m p m with | ℓ i | = s i for all 1 ≤ i ≤ m . Firstly, we show that there exists a simple O ( n ) -time algorithm if the size of the alphabet is unbounded, where n is the length of the output string. Secondly, we present an O ( n ) -time algorithm to compute a string over an alphabet of the smallest size. Thirdly, we show how to compute only the size of the smallest alphabet in O ( m ) time. Fourthly, we give an O ( m ) -time algorithm to compute an O ( m ) -size representation of a string over an alphabet of the smallest size. Finally, we propose an efficient algorithm to enumerate all strings whose Lyndon factorizations correspond to S . [ABSTRACT FROM AUTHOR]

Two space efficient algorithms to solve the L C S k problem and L C S ≥ k problem are presented in this paper. The algorithms improve the time and space complexities of the algorithms of Benson et al. [4] . The space cost of the first algorithm to solve the L C S k problem is reduced from O ( n 2 ) to O ( k n ) , if the size of the two input sequences are both n . The time and space costs of the second algorithm to solve the L C S ≥ k problem are both improved. The time cost is reduced from O ( k n 2 ) to O ( n 2 ) , and the space cost is reduced from O ( n 2 ) to O ( k n ) . In the case of k = O ( 1 ) , the two algorithms are both linear space algorithms. [ABSTRACT FROM AUTHOR]

In this paper we present improved results on the problem of counting triangles in edge streamed graphs. For graphs with m edges and at least T triangles, we show that an extra look over the stream yields a two-pass streaming algorithm that uses O ( m ε 2.5 T polylog ( m ) ) space and outputs a ( 1 + ε ) approximation of the number of triangles in the graph. This improves upon the two-pass streaming tester of Braverman, Ostrovsky and Vilenchik, ICALP 2013, which distinguishes between triangle-free graphs and graphs with at least T triangle using O ( m T 1 / 3 ) space. Also, in terms of dependence on T , we show that more passes would not lead to a better space bound. In other words, we prove there is no constant pass streaming algorithm that distinguishes between triangle-free graphs from graphs with at least T triangles using O ( m T 1 / 2 + ρ ) space for any constant ρ ≥ 0 . [ABSTRACT FROM AUTHOR]

Just as ordinary hypergraphs are a generalization of graphs, directed hypergraphs (DH) are a natural generalization of digraphs. A DH consists of a set of vertices V and a set of hyperarcs H , where a hyperarc is a pair < S , v > , S non empty subset of V and v ∈ V . DHs have a variety of applications: they have been used to represent functional dependency in databases, Horn formulae in propositional logic, and–or graphs, context free grammars etc. In the paper, after providing a brief historical introduction on the notion of DH and some relevant applications, various problems regarding DHs are surveyed and analyzed. In particular we consider the complexity of the reachability problem (together with its application in the related satisfiability problem for Horn CNF formulae) and the computation of transitive closure and transitive reduction of directed hypergraphs (together with its application to the computation of minimum coverings for a set of functional dependencies). Finally a short introduction to the problem of computing shortest hyperpaths in directed hypergraphs is provided. [ABSTRACT FROM AUTHOR]

Abstract: Faugère’s algorithm is one of the fastest algorithms to compute Gröbner bases. It uses two criteria namely the criterion and the IsRewritten criterion to detect the useless critical pairs (see Faugère (2002) ). The IsRewritten criterion has been used in the algorithm, but it has not been explicitly declared in the related paper. In this paper, we give first a complete proof for the IsRewritten criterion and then using a signature structure on Buchberger’s algorithm, we apply this criterion on Buchberger’s algorithm. We have implemented a new algorithm (based on the above results) in Maple to compute a Gröbner basis of a general ideal and we evaluate its performance via some examples. [Copyright &y& Elsevier]

Abstract: The paper describes and analyzes a method for computing border bases of a zero-dimensional ideal . The criterion used in the computation involves specific commutation polynomials, and leads to an algorithm and an implementation extending the ones in [B. Mourrain, Ph. Trébuchet, Generalised normal forms and polynomial system solving, in: M. Kauers (Ed.), Proc. Intern. Symp. on Symbolic and Algebraic Computation, ACM Press, New-York, 2005, pp. 253–260]. This general border basis algorithm weakens the monomial ordering requirement for Gröbner bases computations. It is currently the most general setting for representing quotient algebras, embedding into a single formalism Gröbner bases, Macaulay bases and a new representation that does not fit into the previous categories. With this formalism, we show how the syzygies of the border basis are generated by commutation relations. We also show that our construction of normal form is stable under small perturbations of the ideal, if the number of solutions remains constant. This feature has a huge impact on practical efficiency, as illustrated by the experiments on classical benchmark polynomial systems, at the end of the paper. [Copyright &y& Elsevier]

Abstract: In this paper, we prove two general theorems on monotone Boolean functions which are useful for constructing a learning algorithm for monotone Boolean functions under the uniform distribution. A monotone Boolean function is called fair if it takes the value 1 on exactly half of its inputs. The first result proved in this paper is that a single variable function has the minimum correlation with the majority function among all fair monotone functions. This proves the conjecture by Blum et al. (1998, Proc. 39th FOCS, pp. 408–415) and improves the performance guarantee of the best known learning algorithm for monotone Boolean functions under the uniform distribution they proposed. Our second result is on the relationship between the influences and the average sensitivity of a monotone Boolean function. The influence of variable on f is defined as the probability that differs from where x is chosen uniformly from and means x with its ith bit flipped. The average sensitivity of f is defined as the sum of the influences over all variables . We prove that a somewhat unintuitive result which says if the influence of every variable on a monotone Boolean function is small, i.e., for some constant , then the average sensitivity of the function must be large, i.e., . We also discuss how to apply this result to the construction of a new learning algorithm for monotone Boolean functions. [Copyright &y& Elsevier]

Abstract: This paper shows an asymptotically tight analysis of the Certified Write-All algorithm called AWT that was introduced by Anderson and Woll, SIAM J. Comput. 26 (1997) 1277, and a method for creating near-optimal instances of the algorithm. This algorithm is the best known deterministic algorithm that can be used to simulate n synchronous parallel processors on n asynchronous processors. The algorithm is instantiated with q permutations on , where q can be chosen from a wide range of values. When implementing a simulation on a specific parallel system with n processors, one would like to select the best possible value of q and the best possible q permutations, in order to maximize the efficiency of the simulation. This paper shows that work complexity of any instance of AWT is , where q is the number of permutations selected, and C is a value related to their combinatorial properties. The choice of q turns out to be critical for obtaining an instance of the AWT algorithm with near-optimal work. For any , and any large enough n, work of any instance of the algorithm must be at least . Under certain conditions, however, that q is about and for infinitely many large enough n, this lower bound can be nearly attained by instances of the algorithm that use certain q permutations and have work at most . The paper also shows a penalty for not selecting q well. When q is significantly away from , then work of any instance of the algorithm with this displaced q must be considerably higher than otherwise. [Copyright &y& Elsevier]

In this paper we establish approximation preserving reductions between scheduling problems in which jobs either consume some raw materials, or produce some intermediate products, and variants of the knapsack problem. Through the reductions, we get new approximation algorithms, as well as inapproximability results for the scheduling problems. [ABSTRACT FROM AUTHOR]

Abstract: Circular strings are different from linear strings in that the last symbol is considered to precede the first symbol. Even though circular strings are biologically important, only a few efforts have been made to solve computational problems on circular strings. In this paper, we introduce consensus problems for circular strings of length and present the first non-trivial algorithms to find a consensus and an optimal alignment for circular strings by the Hamming distance. They are -time algorithms for three circular strings and an -time algorithm for four circular strings. Our algorithms are times faster than the naïve algorithms directly using the solutions for the linear consensus problems, which take time for three circular strings and time for four circular strings. This speedup was achieved by reducing the problems into correlations and by formulating and solving systems of linear equations. Moreover, our algorithms use only space. [Copyright &y& Elsevier]

Abstract: In this paper, we introduce an generic framework for the mining of sequences under various constraints. More precisely, we study the enumeration of all partitions of a word into multisets of subsequences. We show that using additional predicates, this generator can be used for frequent subsequences and substrings mining. We define the transition graph whose vertices are multisets of words and arcs are transitions between multisets. We show that is a directed acyclic graph and it admits a covering tree. We use to propose a generic algorithm that enumerates all multisets that satisfies a set of predicates, without redundancy. [Copyright &y& Elsevier]

Abstract: Suffix trees are inherently asymmetric: prefix extensions only cause a few updates, while suffix extensions affect all suffixes causing a wave of updates. In his elegant linear-time on-line suffix tree algorithm Ukkonen relaxed the prevailing suffix tree representation and introduced two changes to avoid repeated structural updates and circumvent the inherent complexity of suffix extensions: (1) open ended edges that enjoy gratuitous leaf updates, and (2) the omission of implicit nodes. In this paper we study the implicit nodes as the suffix tree evolves. We partition the suffix tree’s edges into collections of similar edges called bands, where implicit nodes exhibit identical behavior, and generalize the notion of open ended edges to allow implicit nodes to “float” within bands, only requiring updates when moving from one band to the next, adding up to only updates. We also show that internal implicit nodes are separated from each other by explicit suffix tree nodes and that all external implicit nodes are related to the same periodicity. These new properties may be used to keep track of the waves of implicit node updates and to build the suffix tree on-line in amortized linear time, providing access to all the implicit nodes in worst-case constant time. [Copyright &y& Elsevier]

Abstract: Automated synthesis from behavioural specifications, such as transition systems, is an attractive way of constructing correct concurrent systems. In this paper, we investigate the synthesis of Petri nets which use special connections between transitions and places. Along these a/sync connections tokens can be transferred instantaneously between transitions executed in a single step. We show that for Place/Transition nets with a/sync connections the synthesis problem can be treated within the general approach based on regions of step transition systems. We also show that the problem is decidable for finite transition systems, and outline a suitable construction algorithm. [Copyright &y& Elsevier]

Abstract: Euler’s integer partition theorem, which states that the number of partitions of an integer into odd integers is equal to the number of partitions into distinct integers, ranks 16 in Wells’ list of the most beautiful theorems (Wells, 1990) . In this paper, we use the algorithmic method to evaluate the complexity of mathematical statements developed in Calude et al. (2006) and Calude and Calude (2009, 2010) and to show that Euler’s theorem is in class , the same complexity class as the Riemann hypothesis. [Copyright &y& Elsevier]

Abstract: This paper presents a new polynomial-time algorithm to solve the minimum cost tension problem. It runs in -time, where denote the number of nodes, number of arcs, and maximum arc capacity value of an arc cost, respectively. The algorithm improves the -time algorithm of Maurras (1994) . Also our algorithm, under the similarity assumption (Gabow, 1985) , runs in -time, which improves the -time algorithm of Hadjiat and Maurras (1997) . [Copyright &y& Elsevier]

Abstract: In image processing, the distance transform (DT), in which each object grid point is assigned the distance to the closest background grid point, is a powerful and often used tool. In this paper, distance functions defined as minimal cost-paths are used and a number of algorithms that can be used to compute the DT are presented. We give proofs of the correctness of the algorithms. [Copyright &y& Elsevier]

Abstract: In this paper we introduce an algorithm which solves the membership problem of Petri net controlled grammars without -rules and cyclic rules. We define a conditional tree which is a modified derivation tree of a context-free grammar with information about control by a Petri net. It is shown that a conditional tree is cancelled to a derivation tree without conditions if and only if there is a derivation under the control of the Petri net from the start symbol to a word which is the yielding of the conditional tree. Then the Earley’s algorithm is extended to make a conditional tree in addition to parse a word. Thus the word is generated by a given Petri net controlled grammar if and only if the resulting conditional tree is cancelled to a tree of no condition. The time complexity of the algorithm is nondeterministic polynomial of the length of an input word. Therefore the class of languages generated by Petri net controlled grammars without -rules and cyclic rules is included in the class of context-sensitive languages. [Copyright &y& Elsevier]

Abstract: A graph is called an interval graph if there exists a set of intervals corresponding to the vertex set of and two vertices are adjacent to each other if and only if the two corresponding intervals are intersecting with each other. In this paper, we apply the reliability-based backup 2-center modal proposed by Wang, Wu and Chao, in which each server may fail with a given probability, to interval graphs and present an time algorithm. [Copyright &y& Elsevier]

Abstract: Let denote an -vertex and -edge graph in which is a function mapping each vertex to a positive weight and is a function mapping each edge to a positive length . Given a positive integer , the -Center problem involves finding a set with vertices of to be the locations for building facilities. The objective is to minimize the maximum weighted distance from each vertex in – to its nearest vertex in . This paper considers a practical restriction: the induced subgraph of the selected vertices must be connected. The new variant is called the Connected -Center problem (the problem). For each fixed integer , on block graphs with exactly blocks, we first show that the problem is NP-hard when (1) , for all vertices , and , for all edges , and (2) , for all vertices , and , for all edges , respectively. Second, an -time algorithm for solving the problem on block graphs with unit vertex-weights and unit edge-lengths is proposed. Then, the algorithmic result is extended to handle the situation in which some vertices in cannot be included to form feasible solutions. The complexity of the extended algorithm is also . [Copyright &y& Elsevier]

Abstract: The maxima-finding is a fundamental problem in computational geometry with many applications. In this paper, a volume first maxima-finding algorithm is proposed. It is proved that the expected running time of the algorithm is when choosing points from CI distribution, which is a new theoretical result when the points belong to dimensional space. Experimental results and theoretical analysis indicate that the algorithm runs faster than the Move-To-Front maxima-finding algorithm. [Copyright &y& Elsevier]

Abstract: In this paper, we consider an online non-preemptive scheduling problem on two related machines, where at most jobs are allowed to be rearranged, but only after all jobs have been revealed and (temporarily) scheduled. We minimize the makespan, and we call the problem as Online scheduling with bounded rearrangement at the end (BRE), which is a semi-online problem. Jobs arrive one by one over list. After all the jobs have been arrived and scheduled, we are informed that the input sequence is over; then at most already scheduled jobs can be reassigned. With respect to the worst case ratio, we close the gap between the lower bound and upper bound, improving the previous result as well. Especially, for the lower bound, (i) for an improved lower bound is obtained, which is better than (Liu et al. (2009) ); (ii) for , an improved lower bound is obtained, which is better than (Liu et al. (2009) ). For the upper bound, (i) for and , a new upper bound is obtained, which is optimal and better than the one in Liu et al. (2009) ; (ii) for and , an upper bound is proposed, which is optimal and better than the previous one in Liu et al. (2009) ; (iii) for and , an upper bound is obtained, which is also optimal and better than the previous one in Liu et al. (2009) . [Copyright &y& Elsevier]

Abstract: We study the problem of matching applicants to jobs under one-sided preferences; that is, each applicant ranks a non-empty subset of jobs under an order of preference, possibly involving ties. A matching is said to be more popular than if the applicants that prefer to outnumber those that prefer to . A matching is said to be popular if there is no matching more popular than it. Equivalently, a matching is popular if for all matchings , where is the number of applicants that prefer to . Previously studied solution concepts based on the popularity criterion are either not guaranteed to exist for every instance (e.g., popular matchings) or are NP-hard to compute (e.g., least unpopular matchings). This paper addresses this issue by considering mixed matchings. A mixed matching is simply a probability distribution over matchings in the input graph. The function  that compares two matchings generalizes in a natural manner to mixed matchings by taking expectation. A mixed matching is popular if for all mixed matchings . We show that popular mixed matchings always exist and we design polynomial time algorithms for finding them. Then we study their efficiency and give tight bounds on the price of anarchy and price of stability of the popular matching problem. [Copyright &y& Elsevier]

Abstract: This paper considers the -Compressive Sensing problem and presents an efficient algorithm that computes an exact solution. The idea consists in reformulating the problem such that it yields a modified Dantzig–Wolfe decomposition that allows to efficiently apply all standard simplex pivoting rules. Experimental results show the superiority of our approach compared to standard linear programming methods. [Copyright &y& Elsevier]

Abstract: In this paper, we prove that -connected graphs have either a dominating path or two disjoint paths, wherein the length of the two paths is bounded by the minimum among and a parameter defined on the neighborhood condition of any four independent vertices of the graph. [Copyright &y& Elsevier]

Abstract: Borodin, Nielsen and Rackoff  introduced the class of priority algorithms as a framework for modeling deterministic greedy-like algorithms. In this paper we address the effect of randomization in greedy-like algorithms. More specifically, we consider approximation ratios within the context of randomized priority algorithms. As case studies, we prove inapproximation results for two well-studied optimization problems, namely facility location and makespan scheduling. [Copyright &y& Elsevier]

Abstract: The traditional trend of DNA computing aims at solving computationally intractable problems. The minimum bisection problem (MBP) is a well-known NP-hard problem, which is intended to partition the vertices of a given graph into two equal halves so as to minimize the number of those edges with exactly one end in each half. Based on a biologically inspired computational model, this paper describes a novel algorithm for the minimum bisection problem, which requires a time cost and a DNA strand length that are linearly proportional to the instance size. [Copyright &y& Elsevier]

Abstract: The goal of the Cluster Editing problem is to make the fewest changes to the edge set of an input graph such that the resulting graph is a disjoint union of cliques. This problem is NP-complete but recently, several parameterized algorithms have been proposed. In this paper, we present a number of surprisingly simple search tree algorithms for Weighted Cluster Editing assuming that edge insertion and deletion costs are positive integers. We show that the smallest search tree has size for edit cost , resulting in the currently fastest parameterized algorithm, both for this problem and its unweighted counterpart. We have implemented and compared our algorithms, and achieved promising results. 1 [1] This is an extended version of two articles published in: Proc. of the 6th Asia Pacific Bioinformatics Conference, APBC 2008, in: Series on Advances in Bioinformatics and Computational Biology, vol. 5, Imperial College Press, pp. 211–220; and in: Proc. of the 2nd Conference on Combinatorial Optimization and Applications, COCOA 2008, in: LNCS, vol. 5038, Springer, pp. 289–302. [Copyright &y& Elsevier]

Abstract: This paper studies online scheduling of unit length jobs on a parallel batching machine with the help of lookahead. The objective is to maximize the number of early jobs. Denote by the size of each batch with in the unbounded batching and in the bounded batching. In the lookahead model, at a time instant , an online algorithm can foresee all jobs that will arrive in the time segment . When , we show that a simple greedy online algorithm (independent of the value of ) has a best possible competitive ratio of , where is the number of jobs. This means that lookahead is useless when . When , we establish the upper bounds (for ) and (for ) of competitive ratios, and provide an online algorithm of competitive ratios (for ) and (for ). [Copyright &y& Elsevier]

Abstract: The paper is devoted to demonstrating a randomized algorithm for determining a dominating set in a given graph having a maximum degree of five. The algorithm follows the Las Vegas technique. Furthermore, the concept of a 2-separated collection of subsets of vertices in graphs is used. The suggested algorithm is based on a condition of the upper bound of the cardinality of a local dominating set. If the condition is not satisfied, then the algorithm halts with an appropriate message. Otherwise, the algorithm determines the dominating set. The given algorithm is considered a polynomial-time approximation one. [Copyright &y& Elsevier]

Abstract: Let be a graph without isolated vertices. For a positive integer , a set is a -distance paired-dominating set if each vertex in is within distance of a vertex in and the subgraph induced by contains a perfect matching. In this paper, we present two linear time algorithms to find a minimum cardinality -distance paired-dominating set in interval graphs and block graphs, which are two subclasses of chordal graphs. In addition, we present a characterization of trees with unique minimum -distance paired-dominating set. [Copyright &y& Elsevier]

Abstract: Let be a simple graph without isolated vertices. A vertex set is a paired-dominating set if every vertex in has a neighbor in and the induced subgraph has a perfect matching. In this paper, we investigate the approximation hardness of paired-domination in graphs. For weighted paired-domination, an approximation algorithm in general graphs and an exact dynamic programming style algorithm in trees are also given. [Copyright &y& Elsevier]

Abstract: We consider in this paper the scheduling of families of jobs in which both processing and delivery are coordinated together. Only one vehicle is available to deliver the jobs to specified customers. The jobs can be processed together to form processing batches on the machine and setups of batches are required when the machine is changing from one family to another. Jobs from different families cannot be transported together by the vehicle. The objective is to minimize the time when the vehicle finishes delivering the last delivery batch to its customer and returns to the machine. We propose an -time optimal algorithm for the scheduling problem under the group technology assumption. For the scheduling problem without the group technology assumption, we show that the problem is NP-hard and give an -time dynamic programming algorithm, where is the number of jobs, and is the number of families; we also provide a heuristic algorithm with a performance ratio of 3/2. [Copyright &y& Elsevier]

Abstract: We show that the absolute worst case time complexity for Hopcroft’s minimization algorithm applied to unary languages is reached only for deterministic automata or cover automata following the structure of the de Bruijn words. A previous paper by Berstel and Carton gave the example of de Bruijn words as a language that requires steps in the case of deterministic automata by carefully choosing the splitting sets and processing these sets in a FIFO mode for the list of the splitting sets in the algorithm. We refine the previous result by showing that the Berstel/Carton example is actually the absolute worst case time complexity in the case of unary languages for deterministic automata. We show that the same result is valid also for the case of cover automata and an algorithm based on the Hopcroft’s method used for minimization of cover automata. We also show that a LIFO implementation for the splitting list will not achieve the same absolute worst time complexity for the case of unary languages both in the case of regular deterministic finite automata or in the case of the deterministic finite cover automata as defined by S. Yu. [Copyright &y& Elsevier]

Abstract: Reconstructing the evolutionary history of a set of species is a fundamental problem in biology and methods for solving this problem are gaged based on two characteristics: accuracy and efficiency. Neighbor Joining (NJ) is a so-called distance-based method that, thanks to its good accuracy and speed, has been embraced by the phylogeny community. It takes the distances between taxa and produces in time a phylogenetic tree, i.e., a tree which aims to describe the evolutionary history of the taxa. In addition to performing well in practice, the NJ algorithm has optimal reconstruction radius. The contribution of this paper is twofold: (1) we present an algorithm called Fast Neighbor Joining (FNJ) with optimal reconstruction radius and optimal run time complexity and (2) we present a greatly simplified proof for the correctness of NJ. Initial experiments show that FNJ in practice has almost the same accuracy as NJ, indicating that the property of optimal reconstruction radius has great importance to their good performance. Moreover, we show how improved running time can be achieved for computing the so-called correction formulas. [Copyright &y& Elsevier]

Abstract: Algorithms based on upper confidence bounds for balancing exploration and exploitation are gaining popularity since they are easy to implement, efficient and effective. This paper considers a variant of the basic algorithm for the stochastic, multi-armed bandit problem that takes into account the empirical variance of the different arms. In earlier experimental works, such algorithms were found to outperform the competing algorithms. We provide the first analysis of the expected regret for such algorithms. As expected, our results show that the algorithm that uses the variance estimates has a major advantage over its alternatives that do not use such estimates provided that the variances of the payoffs of the suboptimal arms are low. We also prove that the regret concentrates only at a polynomial rate. This holds for all the upper confidence bound based algorithms and for all bandit problems except those special ones where with probability one the payoff obtained by pulling the optimal arm is larger than the expected payoff for the second best arm. Hence, although upper confidence bound bandit algorithms achieve logarithmic expected regret rates, they might not be suitable for a risk-averse decision maker. We illustrate some of the results by computer simulations. [Copyright &y& Elsevier]

Abstract: This paper considers two semi-online scheduling problems, one with known optimal value and the other with known total sum, on two uniform machines with a machine speed ratio of . For the first problem, we provide an optimal algorithm for , and improved algorithms or/and lower bounds for , over which the optimal algorithm is unknown. As a result, the largest gap between the competitive ratio and the lower bound decreases to 0.02192. For the second problem, we also present algorithms and lower bounds for . The largest gap between the competitive ratio and the lower bound is 0.01762, and the length of the interval over which the optimal algorithm is unknown is 0.47382. Our algorithms and lower bounds for these two problems provide insights into their differences, which are unusual from the viewpoint of the known results on these two semi-online scheduling problems in the literature. [Copyright &y& Elsevier]

Abstract: This paper studies the dynamic bin packing problem, in which items arrive and depart at arbitrary times. We want to pack a sequence of unit fractions items (i.e., items with sizes for some integer ) into unit-size bins, such that the maximum number of bins ever used over all time is minimized. Tight and almost-tight performance bounds are found for the family of any-fit algorithms, including first-fit, best-fit, and worst-fit. In particular, we show that the competitive ratio of best-fit and worst-fit is 3, which is tight, and the competitive ratio of first-fit lies between 2.45 and 2.4942. We also show that no on-line algorithm is better than 2.428-competitive. [Copyright &y& Elsevier]

Abstract: A numerical elimination method is presented in this paper for floating-point computation in polynomial algebra. The method is designed to calculate one or more polynomials in an elimination ideal by a sequence of matrix rank/kernel computation. The method is reliable in numerical computation with verifiable stability and a sensitivity measurement. Computational experiment shows that the method possesses significant advantages over classical resultant computation in numerical stability and in producing eliminant polynomials with lower degrees and fewer extraneous factors. The elimination algorithm combined with an approximate GCD finder appears to be effective in solving polynomial systems for positive dimensional solutions. [Copyright &y& Elsevier]

Abstract: In this paper, we study the conditions in which the random hill-climbing algorithm (1 + 1)-EA compares favorably to other evolutionary algorithms (EAs) in terms of fitness function distribution at a given iteration and with respect to the average optimization time. Our approach is applicable when the reproduction operator of an evolutionary algorithm is dominated by the mutation operator of the (1 + 1)-EA. In this case one can extend the lower bounds obtained for the expected optimization time of the (1 + 1)-EA to other EAs based on the dominated reproduction operator. This method is demonstrated on the sorting problem with HAM landscape and the exchange mutation operator. We consider several simple examples where the (1 + 1)-EA is the best possible search strategy in the class of the EAs. [Copyright &y& Elsevier]

Abstract: Evolutionary algorithms (EAs) find numerous applications, and practical knowledge on EAs is immense. In practice, sophisticated population-based EAs employing selection, mutation and crossover are applied. In contrast, theoretical analysis of EAs often concentrates on very simple algorithms such as the (1+1) EA, where the population size equals 1. In this paper, the question is addressed whether the use of a population by itself can be advantageous. A population-based EA that neither makes use of crossover nor any diversity-maintaining operator is investigated on an example function. It is shown that an increase of the population size by a constant factor decreases the expected runtime from exponential to polynomial. Thereby, the best gap known so far is improved from superpolynomial vs. polynomial to exponential vs. polynomial. Moreover, it is proved that the exponential and polynomial runtime bounds occur with a probability exponentially close to one if the population size is a constant (resp., a small polynomial). Finally, a second example function, where only a small population leads to a polynomial runtime, and a hierarchy result on the appropriate population size are presented. The analyses show formally how the population size can lead to different attractors in the search space. [Copyright &y& Elsevier]

Abstract: Modern applications increasingly require the storage of data beyond relational structure. The challenge of providing well-founded data models that can handle complex objects such as lists, sets, multisets, unions and references has not been met yet in a completely satisfactory way. The success of such data models will greatly depend on the existence of automated database design techniques that generalise achievements from relational databases. In this paper, we study the implication problem of functional dependencies (FDs) in the presence of records, sets, multisets and lists. Database schemata are defined as nested attributes, database instances as nested relations and FDs are defined in terms of subattributes of the database schema. The expressiveness of FDs deviates fundamentally from previous approaches in different data models including the nested relational data model and XML. The implication problem is to decide whether for an arbitrary database schema, and an arbitrary set of FDs defined on that schema, every database instance that satisfies all FDs in also satisfies . The difficulty in generalising the solution from the relational data model to the presence of sets and multisets is caused by the fact that the value on the join of subattributes is no longer determined by the values on the subattributes. Based on the notion of a unit, we propose to decompose the database schema in such a way that the closure of a set of nested attributes can be computed on the components of the schema. The implementation of the algorithm is based on a representation theorem for Brouwerian algebras. The main contribution is the proof that the algorithm works correctly and in polynomial-time in the size of the input. Defining the size of the input is not trivial since the measure should both generalise the one that is used for relational databases and do justice to the presence of sets and multisets. Our solution to the implication problem allows to solve other important problems that occur in database design. We present polynomial-time algorithms to determine non-redundant covers of sets of FDs, and to decide whether a given set of subattributes forms a superkey. [Copyright &y& Elsevier]

Abstract: Double-loop networks have been widely studied as an architecture for local area networks. It is well known that the minimum distance diagram of a double-loop network yields an L-shape. Given a positive integer , it is desirable to find a double-loop network with its diameter being the minimum among all double-loop networks with nodes. Since the diameter of a double-loop network can be easily computed from its L-shape, one method is to start with a desirable L-shape and then find a double-loop network to realize it. This is a problem discussed by many authors [F. Aguiló, M.A. Fiol, An efficient algorithm to find optimal double loop networks, Discrete Math. 138 (1995) 15–29, R.C. Chan, C.Y. Chen, Z.X. Hong, A simple algorithm to find the steps of double-loop networks, Discrete Appl. Math. 121 (2002) 61–72, C.Y. Chen, F.K. Hwang, The minimum distance diagram of double-loop networks, IEEE Trans. Comput. 49 (2000) 977–979, P. Esqué, F. Aguiló, M.A. Fiol, Double commutative-step diagraphs with minimum diameters, Discrete Math. 114 (1993) 147–157] and it has been open for a long time whether this problem can be solved in time. In this paper, we will provide a simple and efficient -time algorithm for solving this problem. [Copyright &y& Elsevier]

Abstract: Research on a new metaheuristic for optimization is often initially focused on proof-of-concept applications. It is only after experimental work has shown the practical interest of the method that researchers try to deepen their understanding of the method''s functioning not only through more and more sophisticated experiments but also by means of an effort to build a theory. Tackling questions such as “how and why the method works’’ is important, because finding an answer may help in improving its applicability. Ant colony optimization, which was introduced in the early 1990s as a novel technique for solving hard combinatorial optimization problems, finds itself currently at this point of its life cycle. With this article we provide a survey on theoretical results on ant colony optimization. First, we review some convergence results. Then we discuss relations between ant colony optimization algorithms and other approximate methods for optimization. Finally, we focus on some research efforts directed at gaining a deeper understanding of the behavior of ant colony optimization algorithms. Throughout the paper we identify some open questions with a certain interest of being solved in the near future. [Copyright &y& Elsevier]

Abstract: The paper presents a compositional approach to the verification of CTL properties over reactive systems. Both symbolic model-checking (SMC) and deductive verification are considered. Both methods are based on two decomposition principles. A general state formula is decomposed into basic state formulas which are CTL formulas with no embedded path quantifiers. To deal with arbitrary basic state formulas, we introduce another reduction principle which replaces each basic path formula, i.e., path formulas whose principal operator is temporal and which contain no embedded temporal operators or path quantifiers, by a newly introduced boolean variable which is added to the system. Thus, both the algorithmic and the deductive methods are based on two statification transformations which successively replace temporal formulas by assertions which contain no path quantifiers or temporal operators. Performing these decompositions repeatedly, we remain with basic assertional formulas, i.e., formulas of the form and for some assertion . In the model-checking method we present a single symbolic algorithm to verify both universal and existential basic assertional properties. In the deductive method we present a small set of proof rules and show that this set is sound and relatively complete for verifying universal and existential basic assertional properties over reactive systems. Together with two proof rules for the decompositions, we obtain a sound and relatively complete proof system for arbitrary CTL properties. Interestingly, the deductive approach for CTL presented here, offers a viable new approach to the deductive verification of arbitrary LTL formulas. [Copyright &y& Elsevier]

Abstract: We investigate the problem of characterizing the solution spaces for timed automata augmented by unknown timing parameters (called timing parameter automata (TPA)). The main contribution of this paper is that we identify three non-trivial subclasses of TPAs, namely, upper-bound, lower-bound and bipartite TPAs, and analyze how hard it is to characterize the solution spaces. As it turns out, we are able to give complexity bounds for the sizes of the minimal (resp., maximal) elements which completely characterize the upward-closed (resp., downward-closed) solution spaces of upper-bound (resp., lower-bound) TPAs. For bipartite TPAs, it is shown that their solution spaces are not semilinear in general. We also extend our analysis to TPAs equipped with counters without zero-test capabilities. [Copyright &y& Elsevier]

Abstract: DFA minimization is an important problem in algorithm design and is based on the notion of DFA equivalence: Two DFA''s are equivalent if and only if they accept the same set of strings. In this paper, we propose a new notion of DFA equivalence (that we call weak-equivalence): We say that two DFA''s are weakly equivalent if they both accept the same number of strings of length k for every k. The motivation for this problem is as follows. A large number of counting problems can be solved by encoding the combinatorial objects we want to count as strings over a finite alphabet. If the collection of encoded strings is accepted by a DFA, then standard algorithms from computational linear algebra can be used to solve the counting problem efficiently. When applying this approach to large-scale applications, the bottleneck is the space complexity since the computation involves a matrix of order if k is the size of the underlying DFA M. This leads to the natural question: Is there a smaller DFA that is weakly equivalent to M? We present an algorithm of time complexity to find a compact DFA weakly equivalent to a given DFA. We illustrate, in the case of a tiling problem, that our algorithm reduces a (strongly minimal) DFA by a factor close to 1/2. [Copyright &y& Elsevier]

The number decision diagram (NDD) has recently been introduced as a powerful representation system for sets of integer vectors. NDDs can notably be used for handling sets defined by arbitrary Presburger formulas, which makes them well suited for representing the set of reachable states of finite-state systems extended with unbounded integer variables. In this paper, we address the problem of counting the number of distinct elements in a set of numbers or, more generally, of vectors, represented by an NDD. We give an algorithm that is able to produce an exact count without enumerating explicitly the vectors, which makes it capable of handling very large sets. As an auxiliary result, we also develop an efficient projection method that allows to construct efficiently NDDs from quantified formulas, and thus makes it possible to apply our counting technique to sets specified by formulas. Our algorithms have been implemented in the verification tool LASH, and applied successfully to various counting problems. [Copyright &y& Elsevier]

A vector algorithm is an algorithm that applies a bounded number of vector operations to an input vector, regardless of the length of the input. In this paper, we describe the links between the existence of vector algorithms and the cascade decompositions of counter-free automata.We show that any computation that can be carried out with a counter-free automaton can be recast as a vector algorithm. Moreover, we show that for a class of automata that is closely related to algorithms in bio-computing, the complexity of the resulting algorithms is linear in the number of transitions of the original automaton. [Copyright &y& Elsevier]