waashk/dblp huggingface dataset:
dynamic rank/select structures with applications to run-length encoded texts. given an n-length text over a @s-size alphabet, we propose a framework for dynamic rank/select structures on the text and some of its applications. for a small alphabet with @s@?logn, we propose a two-level structure consisting of a counting scheme and a storing scheme that supports o(logn) worst-case time rank/select operations and o(logn) amortized time insert/delete operations. for a large alphabet with logn
semi-online machine covering for two uniform machines. the machine covering problem deals with partitioning a sequence of jobs among a set of machines, so as to maximize the completion time of the least loaded machine. we study a semi-online variant, where jobs arrive one by one, sorted by non-increasing size. the jobs are to be processed by two uniformly related machines, with a speed ratio of q>=1. each job has to be processed continuously, in a time slot assigned to it on one of the machines. this assignment needs to be performed upon the arrival of the job. the length of the time slot, which is required for a specific job to run on a given machine, is equal to the size of the job divided by the speed of the machine. we give a complete competitive analysis of this problem by providing an algorithm of the best possible competitive ratio for every q>=1. we first give a tight analysis of the performance of a natural greedy algorithm lpt for the problem. to achieve the best possible performance for the semi-online problem, we use a combination of lpt, together with two alternative algorithms which we design. the new algorithms attain the best possible competitive ratios in the two intervals q@?(1,1.5) and q@?(2.4856,1+3), respectively, whereas the greedy algorithm has the best possible competitive ratio for any other q>=1.
on the minimum hitting set of bundles problem. we consider a natural generalization of the classical minimum hitting set problem, the minimum hitting set of bundles problem (mhsb) which is defined as follows. we are given a set e={e"1,e"2,...,e"n} of n elements. each element e"i (i=1,...,n) has a positive cost c"i. a bundleb is a subset of e. we are also given a collection s={s"1,s"2,...,s"m} of m sets of bundles. more precisely, each set s"j (j=1,...,m) is composed of g(j) distinct bundles b"j^1,b"j^2,...,b"j^g^(^j^). a solution to mhsb is a subset e^'@?e such that for every s"j@?s at least one bundle is covered, i.e. b"j^l@?e^' for some l@?{1,2,...,g(j)}. the total cost of the solution, denoted by c(e^'), is @?"{"i"|"e"""i"@?"e"^"'"}c"i. the goal is to find a solution with a minimum total cost. we give a deterministic n(1-(1-1n)^m)-approximation algorithm, where n is the maximum number of bundles per set and m is the maximum number of sets in which an element can appear. this is roughly speaking the best approximation ratio that we can obtain, since by reducing mhsb to the vertex cover problem, it implies that mhsb cannot be approximated within 1.36 when n=2 and n-1-@e when n>=3. it has to be noticed that the application of our algorithm in the case of the mink-sat problem matches the best known approximation ratio.
computational study on planar dominating set problem. recently, there has been significant theoretical progress towards fixed-parameter algorithms for the dominating set problem of planar graphs. it is known that the problem on a planar graph with n vertices and dominating number k can be solved in o(2^o^(^k^)n) time using tree/branch-decomposition based algorithms. in this paper, we report computational results of fomin and thilikos algorithm which uses the branch-decomposition based approach. the computational results show that the algorithm can solve the dominating set problem of large planar graphs in a practical time and memory space for the class of graphs with small branchwidth. for the class of graphs with large branchwidth, the size of instances that can be solved by the algorithm in practice is limited to about one thousand edges due to a memory space bottleneck. the practical performances of the algorithm coincide with the theoretical analysis of the algorithm. the results of this paper suggest that the branch-decomposition based algorithms can be practical for some applications on planar graphs.
the complete inclusion structure of leaf power classes. let k>=2 be an integer and g=(v,e) be a finite simple graph. a tree t is a k-leaf root of g, if v is the set of leaves of t and, for any two distinct x,y@?v, the distance between x and y in t is at most k if and only if xy@?e. we say that g is a k-leaf power if there is a k-leaf root of g. the main result of this paper is that, for all 2@?k
suffix tree characterization of maximal motifs in biological sequences. finding motifs in biological sequences is one of the most intriguing problems for string algorithm designers due to, on the one hand, the numerous applications of this problem in molecular biology and, on the other hand, the challenging aspects of the computational problem. indeed, when dealing with biological sequences it is necessary to work with approximations (that is, to identify fragments that are not necessarily identical, but just similar, according to a given similarity notion), and this complicates the problem. existing algorithms run in time linear with respect to the input size. nevertheless, the output size can be very large due to the approximation (namely exponential in the approximation degree). this often makes the output unreadable, as well as slowing down the inference itself. a high degree of redundancy has been detected in the set of motifs that satisfy traditional requirements, even for exact motifs. moreover, it has been observed many times that only a subset of these motifs, namely the maximal motifs, could be enough to provide the information of all of them. in this paper, we aim at removing such redundancy. we extend some notions of maximality already defined for exact motifs to the case of approximate motifs with hamming distance, and we give a characterization of maximal motifs on the suffix tree. given that this data structure is used by a whole class of motif extraction tools, we show how these tools can be modified to include the maximality requirement without changing the asymptotical complexity.
why greed works for shortest common superstring problem. the shortest common superstring problem (scs) has been extensively studied for its applications in string compression and dna sequence assembly. although the problem is known to be max-snp hard, the simple greedy algorithm performs extremely well in practice. to explain the good performance, previous researchers proved that the greedy algorithm is asymptotically optimal on random instances. unfortunately, the practical instances in dna sequence assembly are very different from the random instances. in this paper we explain the good performance of the greedy algorithm by using the smoothed analysis. we show that, for any given instance i of scs, the average approximation ratio of the greedy algorithm on a small random perturbation of i is 1+o(1). the perturbation defined in the paper is small and naturally represents the mutations of the dna sequence during evolution. due to the existence of the uncertain nucleotides in the output of a dna sequencing machine, we also proposed the shortest common superstring with wildcards problem (scsw). we prove that in the worst case scsw cannot be approximated within the ratio n^1^/^7^-^@e, while the greedy algorithm still has 1+o(1) smoothed approximation ratio.
on the surface area of the (n, k)-star graph. we present an explicit formula for the surface area of the (n,k)-star graph, i.e., the number of nodes at a certain distance from the identity node in the graph, by identifying the unique cycle structures associated with the nodes in the graph, deriving a distance expression in terms of such structures between the identity node of the graph and any other node, and enumerating those cycle structures satisfying the distance restriction. the above surface area derivation process can also be applied to some of the other node symmetric interconnection structures defined on the symmetric group, when the aforementioned distance expression is available.
(r, p)-centroid problems on paths and trees. an instance of the (r,p)-centroid problem is given by an edge and node weighted graph. two competitors, the leader and the follower, are allowed to place p and r facilities, respectively, into the graph. users at the nodes connect to the closest facility. a solution of the (r,p)-centroid problem is a leader placement such that the maximum total weight of the users connecting to any follower placement is as small as possible. we show that the absolute (r,p)-centroid problem is np-hard even on a path which answers a long-standing open question of the complexity of the problem on trees (hakimi, 1990 [10]). moreover, we provide polynomial time algorithms for the discrete (r,p)-centroid on paths and the (1,p)-centroid on trees, and complementary hardness results for more complex graph classes.
meet continuity properties of posets. in this paper we consider a number of properties of posets that are not directed complete: in particular, meet continuous posets, locally meet continuous posets and pi-meet continuous posets are introduced. characterizations of (locally) meet continuous posets are presented. the main results are: (1) a poset is meet continuous iff its lattice of scott closed subsets is a complete heyting algebra; (2) a poset is a meet continuous poset with a lower hereditary scott topology iff its upper topology is contained in its local scott topology and the lattice of all local scott closed sets is a complete heyting algebra; and (3) a poset with a lower hereditary scott topology is meet continuous iff it is locally meet continuous, iff it is pi-meet continuous.
a 3.4713-approximation algorithm for the capacitated multicast tree routing problem. given an underlying communication network represented as an edge-weighted graph g=(v,e), a source node s@?v, a set of destination nodes d@?v, and a capacity k which is a positive integer, the capacitated multicast tree routing problem asks for a minimum cost routing scheme for source s to send data to all destination nodes, under the constraint that in each routing tree at most k destination nodes are allowed to receive the data copies. the cost of the routing scheme is the sum of the costs of all individual routing trees therein. improving on our previous approximation algorithm for the problem, we present a new algorithm which achieves a worst case performance ratio of 2089+7780+54@r, where @r denotes the best known approximation ratio for the steiner minimum tree problem. since @r is about 1.55 at the writing of the paper, the ratio achieved by our new algorithm is less than 3.4713. in comparison, the previously best ratio was 85+54@r~3.5375.
on nfas where all states are final, initial, or both. we examine questions involving nondeterministic finite automata where all states are final, initial, or both initial and final. first, we prove hardness results for the nonuniversality and inequivalence problems for these nfas. next, we characterize the languages accepted. finally, we discuss some state complexity problems involving such automata.
approximate string matching with address bit errors. a string s@?@s^m can be viewed as a set of pairs s={(@s"i,i):i@?{0,...,m-1}}. we consider approximate pattern matching problems arising from the setting where errors are introduced to the location component (i), rather than the more traditional setting, where errors are introduced into the content itself (@s"i). in this paper, we consider the case where bits of i may be erroneously flipped, either in a consistent or transient manner. we formally define the corresponding approximate pattern matching problems, and provide efficient algorithms for their resolution, while introducing some novel techniques.
on locally reversible languages. there exist several works that study the class of reversible languages defined as the union closure of 0-reversible languages, their properties and suitable representations. in this work we define and study the class of locally reversible languages, defined as the union closure of k-reversible languages. we characterize the class and prove that it is a local (positive) variety of formal languages. we also extend the definition of quasi-reversible automata to deal with locally reversible languages and propose a polynomial algorithm to obtain, for any given locally k-reversible language, a quasi-k-reversible automaton.
the complexity of c-words of the form w×w. let p"n(~) denote the number of c^b^@w-words of the form w@?xw with gap n and p"n(k) denote the number of c^~-words of the form w@?xw with length 2k+n and gap n, where n is the length of the word x. [s. brlek, a. ladouceur, a note on differentiable palindromes, theoret. comput. sci. 302 (2003) 167-178] proved that c^~-palindromes are characterized by the left palindromic closure of the prefixes of the well-known kolakoski sequences and revealed an interesting perspective for understanding some of the conjectures. in fact, they found all infinite c^~-palindromes and established p"0(k)=p"1(k)=2 for all k@?n, where n is the set of positive integers. [y.b. huang, about the number of c^~-words of form w@?xw, theoret. comput. sci. 393 (2008) 280-286] obtained p"n(k)=6 for all k@?n and n=2,3,4, and gave all c^b^@w-words of the form w@?xw with gap less than 5, which imply p"n(~)=2 for n=0,1, and p"n(~)=6 for n=2,3,4. in this paper, we prove the following intriguing results: (1) if w@?xw@?c^b^@w and |x|>=7 then the first and last letters of the word x are the same; (2) p"n(~)=14 for n>=5; (3) for every positive integer n, there exists a positive integer h(n) such that for all k@?n, if k>h(n) then p"n(k)=p"5(k) if k is odd and p"n(k)=p"6(k) if k is even, which would help us understand better the complexity of finite c^~-words of the form w@?xw. moreover, we provide all twenty eight c^b^@w-words of the form w@?xw.
optimal movement of mobile sensors for barrier coverage of a planar region. intrusion detection, area coverage and border surveillance are important applications of wireless sensor networks today. they can be (and are being) used to monitor large unprotected areas so as to detect intruders as they cross a border or as they penetrate a protected area. we consider the problem of how to optimally move mobile sensors to the fence (perimeter) of a region delimited by a simple polygon in order to detect intruders from either entering its interior or exiting from it. we discuss several related issues and problems, propose two models, provide algorithms and analyze their optimal mobility behavior.
isolation concepts for clique enumeration: comparison and computational experiments. we do computational studies concerning the enumeration of isolated cliques in graphs. isolation, as recently introduced, measures the degree of connectedness of the cliques to the rest of the graph. isolation helps both in getting faster algorithms for the enumeration of maximal general cliques and in filtering out cliques with special semantics. we compare three isolation concepts and their combination with two enumeration modi for maximal cliques (''isolated maximal'' vs ''maximal isolated''). all studied concepts exhibit the fixed-parameter tractability of the enumeration task with respect to the parameter ''degree of isolation''. we provide a first systematic experimental study of the corresponding enumeration algorithms, using synthetic graphs (in the g"n","m","p model), financial networks, and a music artist similarity network, proposing the enumeration of isolated cliques as a useful instrument in analyzing financial and social networks.
on the longest common parameterized subsequence. the well-known problem of the longest common subsequence (lcs), of two strings of lengths n and m respectively, is o(nm)-time solvable and is a classical distance measure for strings. another well-studied string comparison measure is that of parameterized matching, where two equal-length strings are a parameterized match if there exists a bijection on the alphabets such that one string matches the other under the bijection. all works associated with parameterized pattern matching present polynomial time algorithms. there have been several attempts to accommodate parameterized matching along with other distance measures, as these turn out to be natural problems, e.g., hamming distance, and a bounded version of edit-distance. several algorithms have been proposed for these problems. in this paper we consider the longest common parameterized subsequence problem which combines the lcs measure with parameterized matching. we prove that the problem is np-hard, and then show a couple of approximation algorithms for the problem.
approximation algorithms for orthogonal packing problems for hypercubes. orthogonal packing problems are natural multidimensional generalizations of the classical bin packing problem and knapsack problem and occur in many different settings. the input consists of a set i={r"1,...,r"n} of d-dimensional rectangular items r"i=(a"i","1,...,a"i","d) and a space q. the task is to pack the items in an orthogonal and non-overlapping manner without using rotations into the given space. in the strip packing setting the space q is given by a strip of bounded basis and unlimited height. the objective is to pack all items into a strip of minimal height. in the knapsack packing setting the given space q is a single, usually unit sized bin and the items have associated profits p"i. the goal is to maximize the profit of a selection of items that can be packed into the bin. we mainly focus on orthogonal knapsack packing restricted to hypercubes and our main results are a (5/4+@e)-approximation algorithm for two-dimensional hypercube knapsack packing, also known as square packing, and a (1+1/2^d+@e)-approximation algorithm for d-dimensional hypercube knapsack packing. in addition we consider d-dimensional hypercube strip packing in the case of a bounded ratio between the shortest and longest side of the basis of the strip. we derive an asymptotic polynomial time approximation scheme (aptas) for this problem. finally, we present an algorithm that packs hypercubes with a total profit of at least (1-@e)opt into a large bin (the size of the bin depends on @e). this problem is known as hypercube knapsack packing with large resources. a preliminary version was published in harren [rolf harren, approximating the orthogonal knapsack problem for hypercubes, in: icalp: proc. 33rd international colloquium on automata, languages and programming, 2006, pp. 238-249] but especially for the latter two approximation schemes no details were given due to page limitations.
partitioning graphs into connected parts. the 2-disjoint connected subgraphs problem asks if a given graph has two vertex-disjoint connected subgraphs containing pre-specified sets of vertices. we show that this problem is np-complete even if one of the sets has cardinality 2. the longest path contractibility problem asks for the largest integer ¿ for which an input graph can be contracted to the path p ¿ on ¿ vertices. we show that the computational complexity of the longest path contractibility problem restricted to p ¿-free graphs jumps from being polynomially solvable to being np-hard at ¿= 6, while this jump occurs at ¿= 5 for the 2-disjoint connected subgraphs problem. we also present an exact algorithm that solves the 2-disjoint connected subgraphs problem faster than ${\cal o}^*(2^n)$ for any n-vertex p ¿-free graph. for ¿= 6, its running time is ${\cal o}^*(1.5790^n)$. we modify this algorithm to solve the longest path contractibility problem for p 6-free graphs in ${\cal o}^*(1.5790^n)$ time.
on selecting a maximum volume sub-matrix of a matrix and related problems. given a matrix a@?r^m^x^n (n vectors in m dimensions), we consider the problem of selecting a subset of its columns such that its elements are as linearly independent as possible. this notion turned out to be important in low-rank approximations to matrices and rank revealing qr factorizations which have been investigated in the linear algebra community and can be quantified in a few different ways. in this paper, from a complexity theoretic point of view, we propose four related problems in which we try to find a sub-matrix c@?r^m^x^k of a given matrix a@?r^m^x^n such that (i) @s"m"a"x(c) (the largest singular value of c) is minimum, (ii) @s"m"i"n(c) (the smallest singular value of c) is maximum, (iii) @k(c)=@s"m"a"x(c)/@s"m"i"n(c) (the condition number of c) is minimum, and (iv) the volume of the parallelepiped defined by the column vectors of c is maximum. we establish the np-hardness of these problems and further show that they do not admit ptas. we then study a natural greedy heuristic for the maximum volume problem and show that it has approximation ratio 2^-^o^(^k^l^o^g^k^). our analysis of the greedy heuristic is tight to within a logarithmic factor in the exponent, which we show by explicitly constructing an instance for which the greedy heuristic is 2^-^@w^(^k^) from optimal. when a has unit norm columns, a related problem is to select the maximum number of vectors with a given volume. we show that if the optimal solution selects k columns, then greedy will select @w(k/logk) columns, providing a logk approximation.
protean graphs with a variety of ranking schemes. we introduce a new class of random graph models for complex real-world networks, based on the protean graph model by luczak and pralat. our generalized protean graph models have two distinguishing features. first, they are not growth models, but instead are based on the assumption that a ''steady state'' of large but finite size has been reached. second, the models assume that the vertices are ranked according to a given ranking scheme, and the rank of a vertex determines the probability that that vertex receives a link in a given time step. precisely, the link probability is proportional to the rank raised to the power -@a, where the attachment strength @a is a tunable parameter. we show that the model leads to a power law degree distribution with exponent 1+1/@a for ranking schemes based on a given prestige label, or on the degree of a vertex. we also study a scheme where each vertex receives an initial rank chosen randomly according to a biased distribution. in this case, the degree distribution depends on the distribution of the initial rank. for one particular choice of parameters we obtain a power law with an exponent that depends both on @a and on a parameter determining the initial rank distribution.
automaton semigroups. the concept of an automaton group generalizes easily to semigroups, and the systematic study of this area is beginning. this paper aims to contribute to that study. the basic theory of automaton semigroups is briefly reviewed. various natural semigroups are shown to arise as automaton semigroups. the interaction of certain semigroup constructions with the class of automaton semigroups is studied. semigroups arising from cayley automata are investigated. various open problems and areas for further research are suggested.
a randomized algorithm for determining dominating sets in graphs of maximum degree five. 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.