Search

Abstract When analyzing the computational complexity of well-known puzzles, most papers consider the algorithmic challenge of solving a given instance of (a generalized form of) the puzzle. We take a different approach by analyzing the computational complexity of designing a "good" puzzle. We assume a puzzle maker designs part of an instance, but before publishing it, wants to ensure that the puzzle has a unique solution. Given a puzzle, we introduce the FCP (fewest clues problem) version of the problem: Given an instance to a puzzle, what is the minimum number of clues we must add in order to make the instance uniquely solvable? We analyze this question for the Nikoli puzzles Sudoku, Shakashaka, and Akari. Solving these puzzles is NP -complete, and we show their FCP versions are Σ 2 P -complete. Along the way, we show that the FCP versions of Triangle Partition , Planar 1- in -3 SAT , and Latin Square are all Σ 2 P -complete. We show that even problems in P have difficult FCP versions, sometimes even Σ 2 P -complete, though "closed under cluing" problems are in the (presumably) smaller class NP ; for example, FCP 2 SAT is NP -complete. [ABSTRACT FROM AUTHOR]

Maximal repetitions or runs in strings have a wide array of applications and thus have been extensively studied. In this paper, we extend this notion to 2-dimensions, precisely defining a maximal 2D repetition. We provide initial bounds on the number of maximal 2D repetitions that can occur in an n × n array. The main contribution of this paper is the presentation of the first algorithm for locating all maximal 2D repetitions. The algorithm is efficient and straightforward, with runtime O (n 2 log ⁡ n + ρ) , where n 2 is the size of the input array and ρ is the number of maximal 2D repetitions in the output. [ABSTRACT FROM AUTHOR]

The problem of reducing ϵ -NN to (c , r) -NN is very important in theoretical computer science area and has attracted many research efforts. In this paper a new algorithm for such problem is proposed, which achieves O (log ⁡ n) query time. Comparing with the former algorithms for the same problem, this query time is the lowest, which is the main contribution of this paper. The low query time complexity is achieved by raising the preprocessing time and space complexity. How to reduce the cost added into the two complexities is also discussed in this paper. [ABSTRACT FROM AUTHOR]

Abstract A Boolean Finite Synchronous Dynamical System (BFDS, for short) consists of a finite number of objects that each maintains a boolean state, where after individually receiving state assignments, the objects update their state with respect to object-specific time-independent boolean functions synchronously in discrete time steps. The present paper studies the computational complexity of determining, given a boolean finite synchronous dynamical system, a configuration, which is a boolean vector representing the states of the objects, and a positive integer t , whether there exists another configuration from which the given configuration can be reached in t steps. It was previously shown that this problem, which we call the t -Predecessor Problem, is NP-complete even for t = 1 if the update function of an object is either the conjunction of arbitrary fan-in or the disjunction of arbitrary fan-in. This paper studies the computational complexity of the t -Predecessor Problem for a variety of sets of permissible update functions as well as for polynomially bounded t. It also studies the t -Garden-Of-Eden Problem, a variant of the t -Predecessor Problem that asks whether a configuration has a t -predecessor, which itself has no predecessor. The paper obtains complexity theoretical characterizations of all but one of these problems. [ABSTRACT FROM AUTHOR]

Abstract In this paper, we consider the problems for covering multiple intervals on a line. Given a set B of m line segments (called "barriers") on a horizontal line L and another set S of n horizontal line segments of the same length in the plane, we want to move all segments of S to L so that their union covers all barriers and the maximum movement of all segments of S is minimized. Previously, an O (n 3 log ⁡ n) -time algorithm was given for the case m = 1. In this paper, we propose an O (n 2 log ⁡ n log ⁡ log ⁡ n + n m log ⁡ m) -time algorithm for a more general setting with any m ≥ 1 , which also improves the previous work when m = 1. We then consider a line-constrained version of the problem in which the segments of S are all initially on the line L. Previously, an O (n log ⁡ n) -time algorithm was known for the case m = 1. We present an algorithm of O (m log ⁡ m + n log ⁡ m log ⁡ n) time for any m ≥ 1. These problems may have applications in mobile sensor barrier coverage in wireless sensor networks. [ABSTRACT FROM AUTHOR]

Let B be a set of b blue points and R be a set of r red points in the plane. In this paper we study the problem of finding rectangles that contain the maximum number of blue points without containing any red points, known as the maximum-box problem . First we study this problem for axis-aligned rectangles, and propose an exact worst-case optimal O ( r 2 + r b + b log ⁡ b ) time algorithm using O ( r + b ) space to find all maximum boxes. We also provide a 2-approximation algorithm running in O ( ( r + b ) log ⁡ ( r + b ) ) time and using O ( r + b ) space to find a single maximum box in the axis-aligned case. Then we generalize the exact algorithm for the axis-aligned case to find all arbitrarily oriented maximum boxes leading to a worst-case optimal O ( ( r + b ) 2 ( r + log ⁡ b ) ) time algorithm using O ( ( r + b ) 2 ) space to solve the problem. We conclude the paper by discussing time and space trade-offs. Our results improve the previously best known solutions to the maximum-box problem. [ABSTRACT FROM AUTHOR]

This paper addresses for the first time the problem of MWMR atomic memory in a Mobile Byzantine Agents model. The register is maintained by n servers and faulty (Byzantine) agents move from one server to another and when they are affecting a server, this one behaves arbitrarily. This paper addresses the round-based synchronous communication model. We focus on four Mobile Byzantine Failure models differing in the diagnosis capabilities at server side. We address the case when servers can diagnose their failure state (that is, servers are aware that the mobile Byzantine agent has left), and the case when servers cannot self-diagnose. We first prove lower bounds on the number of servers n necessary to construct a safe register tolerant to the presence of f < n Mobile Byzantine Failures for four Mobile Byzantine Failure models. Additionally, we prove that our lower bounds do not change when the system is affected by any number of transient failures . Furthermore, we propose a parametric algorithm that implements an atomic MWMR register algorithm working in all the above models and matches the lower bounds. Additionally, our algorithm is also self-stabilizing. That is, started in an arbitrary state (i.e. after the occurrence of a transient failure) it is able to self-recover a correct behavior in a finite, bounded number of rounds. Our algorithm tolerates (i) any number of transient failures and (ii) up to f Mobile Byzantine Failures. [ABSTRACT FROM AUTHOR]

Calculating and analyzing the number of spanning trees of graphs (network models) is an important and interesting research project in wide variety of fields, such as mathematics, physics, theoretical computer science, chemistry and so on. The number of spanning trees of graphs (models) displays amounts of information on its structural features and also on some relevant dynamical properties, in particular network security, random walks and percolation. In this paper, firstly, due to lots of graphs (models) are built on the basis of various simple and small elements (components), we provide primarily some helpful network-operation, such as link-operation and merge-operation, to generate more realistic and complicated graphs (models). Secondly, considering reliability of fault-tolerance to random faults and of intrusion-tolerance to selectively remove attacks, synchronization capability and diffusion properties of networks, we present an iterative method (algorithm) for computing the total number of spanning trees. As a pellucid example, we apply our method to tree space and cycle space, notice that it is proved to be indeed a better tool. In order to reflect more widely practical meanings, we study its applications in graph theory, including ladder-graph with zero clustering coefficient, wheel-graph having nonzero clustering coefficient as constituent ingredients of maximal planar graphs. In the rest of this paper, we make a brief summary that the method described by us can be designed a program (algorithm) for obtaining easily the exact number of spanning trees of some models. [ABSTRACT FROM AUTHOR]

It is a well-known result that homomorphic encryption is not secure against adaptive chosen ciphertext attacks (CCA2) because of its malleable property. Very recently, however, Gong et al. proposed a construction asserted to be a CCA2-secure additively homomorphic encryption (AHE) scheme; in their construction, the adversary is not able to obtain a correct answer when querying the decryption oracle on a ciphertext obtained by modifying the challenge ciphertext (Theoretical Computer Science, 2016). Because their construction is very similar to Paillier's AHE, it appeared to support an additively homomorphic property, though they did not specify an evaluation algorithm for the scheme in their paper. In this paper, we present a simple CCA2 attack on their construction by re-randomizing the challenge ciphertext. Furthermore, we look into an additively homomorphic property of their construction. To do this, we first consider a typical candidate for an addition algorithm on ciphertexts, as provided for previous AHE constructions, and establish that it does not function correctly. Subsequently, we provide plausible evidence for the hardness of achieving an additively homomorphic property with their construction. According to our analysis, it seems hard to preserve an additively homomorphic property of their construction without any modification. In addition, as a minor contribution, we point out a flaw in the decryption algorithm of their construction and present a rectified algorithm for correct decryption. [ABSTRACT FROM AUTHOR]

This paper investigates the problem of Byzantine Agreement in a synchronous system where malicious agents can move from process to process, corrupting their host. Earlier works on the problem are based on biased models which, as we argue in the paper, give an unfair advantage either to the correct processes or to the adversary controlling the malicious agents. Indeed, earlier studies of the problem assume that, after a malicious agent has left a process, that process, said to be cured, is able to instantly and accurately detect the fact that it was corrupted in earlier rounds, and thus can take local actions to recover a valid state (Garay's model). We found no justification for that assumption which clearly favors correct processes. Under that model, an algorithm is known for n > 4 t , where n is the number of processes and t the maximum number of malicious agents. The tightness of the bound is however unknown. In contrast, more recent works on the problem remove the assumption on detection and assume instead that a malicious agent may have left corrupted messages in the send queue of a cured process in addition to a corrupted state. As a result, the adversary controlling the malicious agents can corrupt the messages sent by cured processes, in addition to those sent by the newly corrupted ones, thus doubling the number of effective faults. Under that model, which favors the malicious agents, the problem can be solved if and only if n > 6 t . In this paper, we refine the latter model to avoid the above biases. While a cured process may send messages (based on a state corrupted by the malicious agent), it will behave correctly in the way it sends those messages: i.e., send messages according to the algorithm. Surprisingly, in this model we could derive a new non-trivial tight bound for Byzantine Agreement. We prove that at least 5 t + 1 processors are needed in order to tolerate t mobile Byzantine agents and provide a time optimal algorithm that matches this lower bound, altogether with a formal specification of the problem. [ABSTRACT FROM AUTHOR]

In the one-way trading problem, a seller has L units of product to be sold to a sequence σ of buyers u 1 , u 2 , … , u σ arriving online and he needs to decide, for each u i , the amount of product to be sold to u i at the then-prevailing market price p i . The objective is to maximize the seller's revenue. We note that all previous algorithms for the problem need to impose some artificial upper bound M and lower bound m on the market prices, and the seller needs to know either the values of M and m , or their ratio M / m , at the outset. This paper gives a one-way trading algorithm that does not impose any bounds on market prices and whose performance guarantee depends directly on the input. In particular, we give a class of one-way trading algorithms such that for any positive integer h and any positive number ϵ , we have an algorithm A h , ϵ that has competitive ratio O ( log ⁡ r ⁎ ( log ( 2 ) ⁡ r ⁎ ) … ( log ( h − 1 ) ⁡ r ⁎ ) ( log ( h ) ⁡ r ⁎ ) 1 + ϵ ) if the value of r ⁎ = p ⁎ / p 1 , the ratio of the highest market price p ⁎ = max i ⁡ p i and the first price p 1 , is large and satisfies log ( h ) ⁡ r ⁎ > 1 , where log ( i ) ⁡ x denotes the application of the logarithm function i times to x ; otherwise, A h , ϵ has a constant competitive ratio Γ h . We also show that our algorithms are near optimal by showing that given any positive integer h and any one-way trading algorithm A , we can construct a sequence of buyers σ with log ( h ) ⁡ r ⁎ > 1 such that the ratio between the optimal revenue and the revenue obtained by A is Ω ( log ⁡ r ⁎ ( log ( 2 ) ⁡ r ⁎ ) … ( log ( h − 1 ) ⁡ r ⁎ ) ( log ( h ) ⁡ r ⁎ ) ) . A special case of the one-way trading is also studied, in which the L units of product are comprised of L items, each of which must be sold atomically (or equivalently, the amount of product sold to each buyer must be an integer). Furthermore, a complementary problem to the one-way trading problem, say, the one-way buying problem, is studied in this paper. In the one-way buying problem, a buyer wants to purchase one unit of product through a sequence of n sellers v 1 , v 2 , … , v n arriving online, and she needs to decide the fraction to purchase from each v i at the then-prevailing market price p i . Her objective is to minimize the cost. The optimal competitive algorithms whose performance guarantees depend only on the lowest market price p ⁎ = min i ⁡ p i , and one of M and φ , the price fluctuation ratio, are presented. [ABSTRACT FROM AUTHOR]

Finding heavy-elements (heavy-hitters) in streaming data is one of the central, and well-understood tasks. Despite the importance of this problem, when considering the sliding windows model of streaming (where elements eventually expire) the problem of finding L 2 -heavy elements has remained completely open despite multiple papers and considerable success in finding L 1 -heavy elements. Since the L 2 -heavy element problem doesn't satisfy certain conditions, existing methods for sliding windows algorithms, such as smooth histograms or exponential histograms are not directly applicable to it. In this paper, we develop the first polylogarithmic-memory algorithm for finding L 2 -heavy elements in the sliding window model. Our technique allows us not only to find L 2 -heavy elements, but also heavy elements with respect to any L p with 0 < p ≤ 2 on sliding windows. By this we completely “close the gap” and resolve the question of finding L p -heavy elements in the sliding window model with polylogarithmic memory, since it is well known that for p > 2 this task is impossible. We demonstrate a broader applicability of our method on two additional examples: we show how to obtain a sliding window approximation of the similarity of two streams, and of the fraction of elements that appear exactly a specified number of times within the window (the α -rarity problem). In these two illustrative examples of our method, we replace the current expected memory bounds with worst case bounds. [ABSTRACT FROM AUTHOR]

This paper is devoted to the distributed complexity of finding an approximation of the maximum cut (MaxCut) in graphs. A classical algorithm consists in letting each vertex choose its side of the cut uniformly at random. This does not require any communication and achieves an approximation ratio of at least 1 2 in expectation. When the graph is d -regular and triangle-free, a slightly better approximation ratio can be achieved with a randomized algorithm running in a single round. Here, we investigate the round complexity of deterministic distributed algorithms for MaxCut in regular graphs. We first prove that if G is d -regular, with d even and fixed, no deterministic algorithm running in a constant number of rounds can achieve a constant approximation ratio. We then give a simple one-round deterministic algorithm achieving an approximation ratio of 1 d for d -regular graphs when d is odd. We show that this is best possible in several ways, and in particular no deterministic algorithm with approximation ratio 1 d + ϵ (with ϵ > 0) can run in a constant number of rounds. We also prove results of a similar flavor for the MaxDiCut problem in regular oriented graphs, where we want to maximize the number of arcs oriented from the left part to the right part of the cut. [ABSTRACT FROM AUTHOR]

The longest common increasing subsequences (LCIS) problem is to find out a common increasing subsequence with the maximal length of two given sequences A and B. In this paper, we propose an algorithm for solving the LCIS problem with O ((n + L (m − L)) log ⁡ log ⁡ | Σ |) time and O(n) space, where m and n denote the lengths of A and B , respectively, m ≤ n , L denotes the LCIS length, and Σ denotes the alphabet set. The main idea of our algorithm is to extend the answer from some previously feasible solutions, in which the domination function is invoked. To accomplish the extension and domination functions, the data structure of the van Emde Boas tree is utilized. From the time complexity, it is obvious that our algorithm is extremely efficient when L is very small or L is close to m. Some experiments are performed to demonstrate the efficiency of our algorithm. [ABSTRACT FROM AUTHOR]

A mixed domination of a graph G = (V , E) is a mixed set D of vertices and edges such that for every edge or vertex, if it is not in D , then it is adjacent or incident to at least one vertex or edge in D. The Mixed Domination problem is to check whether there is a mixed domination of size at most k in a graph. Mixed domination is a mixture concept of vertex domination and edge domination, and the mixed domination problem has been studied from the view of approximation algorithms, parameterized algorithms, and so on. In this paper, we give a branch-and-search algorithm with running time bound of O ⁎ (4.172 k) , which improves the previous bound of O ⁎ (7.465 k). For kernelization, it is known that the problem parameterized by k in general graphs is unlikely to have a polynomial kernel. We show the problem in planar graphs allows linear kernel by giving a kernel of 11 k − 16 vertices. [ABSTRACT FROM AUTHOR]

The Burrows-Wheeler Transform (BWT) has become since its introduction a key tool for representing large text collections in compressed space while supporting indexed searching: on a text of length n over an alphabet of size σ , it requires O (n lg ⁡ σ) bits of space, instead of the O (n lg ⁡ n) bits required by classical indexes. A challenge for its adoption is to build it within O (n lg ⁡ σ) bits as well. There are some sequential algorithms building it within this space, but no such a parallel algorithm. In this paper we present a PRAM CREW algorithm to build the BWT using O (n lg ⁡ n) work, O (lg 3 ⁡ n / lg ⁡ σ) depth, and O (n lg ⁡ σ) bits. [ABSTRACT FROM AUTHOR]

• A new variant of approximate palindromes called single-arm-gapped palindromes. • Efficient algorithms to compute maximal single-arm-gapped palindromes in a string. • Experimental results to compare the proposed methods in practice. In this paper, we introduce new types of approximate palindromes called single-arm-gapped palindromes (shortly SAGPs). A SAGP contains a gap in either its left or right arm, which is in the form of either w g u c u R w R or w u c u R g w R , where w and u are non-empty strings, w R and u R are respectively the reversed strings of w and u , g is a string called a gap, and c is either a single character or the empty string. Here we call wu and u R w R the arm of the SAGP, and | u v | the length of the arm. We classify SAGPs into two groups: those which have u c u R as a maximal palindrome (type-1), and the others (type-2). We propose several algorithms to compute type-1 SAGPs with longest arms occurring in a given string, based on suffix arrays. Then, we propose a linear-time algorithm to compute all type-1 SAGPs with longest arms, based on suffix trees. Also, we show how to compute type-2 SAGPs with longest arms in linear time. We also perform some preliminary experiments to show practical performances of the proposed methods. [ABSTRACT FROM AUTHOR]

A widely studied model of influence diffusion in social networks represents the network as a graph G = (V , E) , with an integer influence threshold t (v) for each node, and the diffusion process as follows: Initially the members of a chosen set S ⊆ V are influenced and, during each subsequent round, the set of influenced nodes is augmented by including every new node v that has at least t (v) previously influenced neighbours. The general problem is to find a small initial set that influences the whole network. In this paper we extend this model by using incentives to reduce the thresholds of some nodes. The goal is to minimize the total amount of the incentive required to ensure that the information diffusion process terminates within a given number of rounds λ. The problem is hard to approximate in general networks. We present optimal polynomial-time algorithms for paths, cycles, trees, and complete networks for any λ. For the special case λ = 1 , we present a polynomial-time algorithm with a logarithmic approximation guarantee for any network. [ABSTRACT FROM AUTHOR]

We introduce the notion of expandability in the context of automaton semigroups and groups: a word is k-expandable if one can append a suffix to it such that the size of the orbit under the action of the automaton increases by at least k. This definition is motivated by the question which ω -words admit infinite orbits: for such a word, every prefix is expandable. In this paper, we show that, given a word u , an automaton T and a number k as input, it is decidable to check whether u is k -expandable with respect to the action of T. In fact, this can be done in exponential nondeterministic space. From this nondeterministic algorithm, we obtain a bound on the length of a potential orbit-increasing suffix x. Moreover, we investigate the situation if the automaton is invertible and generates a group. In this case, we give an algebraic characterization for the expandability of a word based on its shifted stabilizer. We also give a more efficient algorithm to decide the expandability of a word in the case of automaton groups, which allows us to improve the upper bound on the maximal orbit-increasing suffix length. Then, we investigate the situation for reversible (and complete) automata and obtain that every word is expandable with respect to such automata. Finally, we give a lower bound example for the length of an orbit-increasing suffix. [ABSTRACT FROM AUTHOR]

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 the paper "Linear time algorithm to cover and hit a set of line segments optimally by two axis-parallel squares", Theor. Comput. Sci. 769 (2019) 63–74, the LHIT problem is proposed as follows: For a given set of non-intersecting line segments L = { ℓ 1 , ℓ 2 , ... , ℓ n } in Image 1 , compute two axis-parallel congruent squares S 1 and S 2 of minimum size whose union hits all the line segments in L , and a linear time algorithm was proposed. Later it was observed that the algorithm has a bug. In this corrigendum, we corrected the algorithm. The time complexity of the corrected algorithm is O (n 2). [ABSTRACT FROM AUTHOR]

The locating-chromatic number of a graph G (V , E) is the cardinality of a minimum resolving partition of the vertex set V (G) such that all vertices have distinct coordinates with respect to this partition and every two adjacent vertices not contained in the same partition class. Determining the locating-chromatic number of any tree is a difficult task. In this paper, we propose an algorithm to compute the upper bound on the locating-chromatic number of any tree. To do so, we decompose a tree into caterpillars and then compute the upper bound of the locating-chromatic number of this tree in terms of the ones for these caterpillars. [ABSTRACT FROM AUTHOR]

Let G be an(a) edge(vertex)-colored graph. A path P of G is called a conflict-free path if there is a color that is used on exactly one of the edges(vertices) of P. The graph G is called conflict-free (vertex-)connected if any two distinct vertices of G are connected by a conflict-free path, whereas the graph G is called strongly conflict-free connected if any two distinct vertices u , v of G are connected by a conflict-free path of length of a shortest path between u and v in G. For a connected graph G , the (strong) conflict-free connection number of G , denoted by (s c f c (G)) c f c (G) , is defined as the smallest number of colors that are required to make G (strongly) conflict-free connected. In this paper, we first investigate the question: Given a connected graph G and a coloring c : E (o r V) → { 1 , 2 , ⋯ , k } (k ≥ 1) of G , determine whether or not G is, respectively, conflict-free connected, conflict-free vertex-connected, strongly conflict-free connected under the coloring c. We solve this question by providing polynomial-time algorithms. We then show that the problem of deciding whether s c f c (G) ≤ k (k ≥ 2) for a given graph G is NP-complete. Moreover, we prove that it is NP-complete to decide whether there is a k -edge-coloring (k ≥ 2) of G such that all pairs (u , v) ∈ P (P ⊂ V × V) are strongly conflict-free connected. [ABSTRACT FROM AUTHOR]

In this paper, we consider the (n,3)-MAXSAT problem. The problem is a special case of the Maximum Satisfiability problem with an additional requirement that in the input formula each variable appears at most three times. Here, we improve previous upper bounds for (n,3)-MAXSAT in terms of n (number of variables) and in terms of k (number of clauses that we are required to satisfy). Moreover, we prove that satisfying more clauses than the simple all true assignment is an NP-hard problem. [ABSTRACT FROM AUTHOR]

Rumor Blocking, an important optimization problem in social network, has been extensively studied in the literature. Given social network G = (V , E) and rumor seed set A , the goal is asking for k protector seeds that protect the largest expected number of social individuals by truth. However, the source of rumor is always uncertain, rather than being predicted or being known in advance in the real situations, while rumor spreads like wildfire on the Internet. This paper presents General Rumor Blocking with unpredicted rumor seed set (randomized A) and various personal profits while being protected (weights of nodes in V). We first show that the objective function of this problem is non-decreasing and submodular, and thus a (1 − 1 / e) approximate solution can be returned by greedy approach. We then propose an efficient random algorithm R-GRB which returns a (1 − 1 / e − ε) approximate solution with at least 1 − n − ℓ probability. We show that it runs in O (m (n − r) (k log ⁡ (n − r) + ℓ log ⁡ n) / ε 2) expected time, where m = | E | , n = | V | , r = | A | and k is the number of protector seeds. Finally, we conduct extensive experiments to evaluate the R-GRB and show that it is superior in both theory and experiment. [ABSTRACT FROM AUTHOR]

Path planning is an important and classical problem in theoretical research and practical applications. In the complex and hierarchical space scenarios, path planning faces more difficulties and challenges due to the structural particularity. Considering the directivity of paths in hierarchical spaces, it is more important to guarantee the fluency and efficiency of the paths in hierarchical spaces. In this paper, we introduce a path network planning problem from multi-source to multi-destination in hierarchical spaces, namely Balanced-Flow Path Network Planning (BF-PNP) problem, and prove its NP-completeness. To balance the flow rate among the layers in the space, we propose a batch scheduling algorithm with the objective of minimizing the scheduling time consumption. To evaluate the performance on efficiency and time complexity, we perform a series of simulations and the results indicate the advantages of the proposed algorithm. [ABSTRACT FROM AUTHOR]

Given a social network G and a positive integer k , the influence maximization problem seeks for k nodes in G that can influence the largest number of nodes. This problem has found important applications, and a large amount of works have been devoted to identifying the few most influential users. But most of existing works only focus on the diffusion of a single idea or product in social networks. However, in reality, one company may produce multiple kinds of products and one user may also have multiple adoptions. For multiple kinds of different products with different activation costs and profits, it is crucial for the company to distribute the limited budget among multiple products in order to achieve profit maximization. The Profit Maximization with Multiple Adoptions (PM2A) problem aims to seek for a seed set within the budget to maximize the overall profit. In this paper, a Randomized Modified Greedy (RMG) algorithm based on the Reverse Influence Sampling (RIS) technique is presented for the PM2A problem, which could achieve a (1 − 1 / e − ε) -approximate solution with high probability and is also the best performance ratio of the PM2A problem. Comprehensive experiments on three real-world social networks are conducted, and the results demonstrate that our RMG algorithm outperforms the algorithm proposed in [16] and other heuristics in terms of profit maximization, and could better allocate the budget. [ABSTRACT FROM AUTHOR]

This paper presents a bicriteria approximation algorithm for the minimum submodular cost partial set multi-cover problem (SCPSMC), the goal of which is to find a minimum cost sub-collection of sets to fully cover q percentage of total profit of all elements, where the cost on sub-collections is a submodular function, and an element e with covering requirement r e is fully covered if it belongs to at least r e picked sets. Assuming that the maximum covering requirement r max = max e ∈ E ⁡ r e is a constant and the cost function is nonnegative and submodular, we give a deterministic (b / q ε , (1 − ε)) -bicriteria algorithm for SCPSMC, the output of which fully covers at least (1 − ε) q -percentage of the total profit and the performance ratio is b / q ε , where b = max e ⁡ ( f e r e ) and f e is the number of sets containing element e. [ABSTRACT FROM AUTHOR]

In this paper, we explore some connections between covering arrays (CAs) and set covers (SCs) that already existed in the literature, and in some cases we provide new mappings between these structures. In particular, the devised mappings make feasible an interpretation of weighted budgeted CAs (WBCAs) as weighted budgeted SCs. These connections in turn make it possible to reformulate known greedy heuristics for computing mixed-level CAs and evolve new algorithms for WBCA generation. This also enables importing an upper bound on the size or a lower bound on the covered weight of the generated arrays. We further carry out a comparison of a CA generation strategy that has an analogue in the SC world with one developed specifically for CAs. Moreover, we experiment with several problem instances for CA and WBCA generation, and compare CA solvers versus SC solvers, both in quality of their output size and covered weights, as well as computation time. Our experiments underpin the hypothesis that CA solvers provide solutions of comparable quality to the ones returned by the considered SC solvers, although the latter solvers generally provide solutions of better quality. Nevertheless, CA solvers provide solutions to the respective problem instances much faster. [ABSTRACT FROM AUTHOR]

In this paper we introduce a notion of planarity for graphs that are presented in a streaming fashion. A streamed graph is a stream of edges e 1 , e 2 , ... , e m on a vertex set V. A streamed graph is ω-stream planar with respect to a positive integer window size ω if there exists a sequence of planar topological drawings Γ i of the graphs G i = (V , { e j | i ≤ j < i + ω }) such that the common graph G ∩ i = G i ∩ G i + 1 is drawn the same in Γ i and in Γ i + 1 , for 1 ≤ i ≤ m − ω. The Stream Planarity Problem with window size ω asks whether a given streamed graph is ω -stream planar. We also consider a generalization, where there is an additional backbone graph whose edges have to be present during each time step. These problems are related to several well-studied planarity problems. We show that the Stream Planarity Problem is NP -complete even when the window size is a constant and that the variant with a backbone graph is NP -complete for all ω ≥ 2. On the positive side, we provide O (n + ω m) -time algorithms for (i) the case ω = 1 and (ii) all values of ω provided the backbone graph is 2-connected. Our results improve on the Hanani-Tutte-style algorithm proposed by Schaefer [GD'14] for ω = 1 , which runs in O ((n m) 3) time. [ABSTRACT FROM AUTHOR]

A string X = X [ 1.. n ] , n > 1 , is said to be closed if it has a nonempty proper prefix that is also a suffix, but that otherwise occurs nowhere else in X ; for n = 1 , every X is closed. Closed strings were introduced by Fici in [1] as objects of combinatorial interest. Recently Badkobeh et al. [2] described a variety of algorithms to factor a given string into closed factors. In particular, they studied the Longest Closed Factorization (LCF) problem, which greedily computes the decomposition X = X 1 X 2 ⋯ X k , where X 1 is the longest closed prefix of X , X 2 the longest closed prefix of X with prefix X 1 removed, and so on. In this paper we present an O (log ⁡ n) amortized per character algorithm to compute LCF on-line, where n is the length of the string. We also introduce the Minimum Closed Factorization (MCF) problem, which identifies the minimum number of closed factors that cover X. We first describe an off-line O (n log 2 ⁡ n) -time algorithm to compute M C F (X) , then we present an on-line algorithm for the same problem. In fact, we show that M C F (X) can be computed in O (L log ⁡ n) time from M C F (X ′) , where X ′ = X [ 1.. n − 1 ] , and L is the largest integer such that the suffix X [ n − L + 1.. n ] is a substring of X ′. [ABSTRACT FROM AUTHOR]

A proper (simple) relation algebra is a collection A of binary relations on a set U such that the top element of the algebra is U × U , and A is closed under union, intersection, complementation, composition, converse and contains the identity relation on U. Proper relation algebras can be constructed using U = Z / p Z as a base set using a method due to Comer. The cycle structure of such an algebra must, in general, be determined a posteriori , normally with the aid of a computer. In this paper, we give an improved algorithm for checking the cycle structure that reduces the time complexity from O (p 2) to O (p). [ABSTRACT FROM AUTHOR]

Many networking applications require timely access to recent network measurements, which can be captured using a sliding window model. Maintaining such measurements is a challenging task due to the fast line speed and scarcity of fast memory in routers. In this work, we study the impact of allowing slack in the window size on the asymptotic requirements of sliding window problems. That is, the algorithm can dynamically adjust the window size between W and W (1 + τ) where τ is a small positive parameter. We demonstrate this model's attractiveness by showing that it enables efficient algorithms to problems such as Maximum and General-Summing that require Ω (W) bits even for constant factor approximations in the exact sliding window model. Additionally, for problems that admit sub-linear approximation algorithms such as Basic-Summing and Count-Distinct , the slack model enables a further asymptotic improvement. The main focus of the paper is on the widely studied Basic-Summing problem of computing the sum of the last W integers from { 0 , 1 ... , R } in a stream. While it is known that Ω (W log ⁡ R) bits are needed in the exact window model, we show that approximate windows allow an exponential space reduction for constant τ. Specifically, for τ = Θ (1) , we present a space lower bound of Ω (log ⁡ (R W)) bits. Additionally, we show an Ω (log ⁡ (W / ϵ)) lower bound for RWϵ additive approximations and a Ω (log ⁡ (W / ϵ) + log ⁡ log ⁡ R) bits lower bound for (1 + ϵ) multiplicative approximations. Our work is the first to study this problem in the exact and additive approximation settings. For all settings, we provide memory optimal algorithms that operate in worst case constant time. This strictly improves on the work of [17] for (1 + ϵ) -multiplicative approximation that requires O (ϵ − 1 log ⁡ (R W) log ⁡ log ⁡ (R W)) space and performs updates in O (log ⁡ (R W)) worst case time. Finally, we show asymptotic improvements for the Count-Distinct , General-Summing , and Maximum problems. [ABSTRACT FROM AUTHOR]

In Temporal Logic (TL), a well-formed formula is generally formed by applying rules of its syntax finitely many times. However, under some circumstances, although formulas such as ones expressed by index set expressions , are constructed via applying rules of the syntax infinitely many times, they are possibly still well-formed since their equivalent concise syntax formulas can be found. With this motivation, this paper investigates the relationship between formulas specified by index set expressions and concise syntax by means of fixed-point approach. Firstly, we present two kinds of formulas, namely ⋁ i ∈ N 0 ◯ i Q and ⋁ i ∈ N 0 Q i , and prove they are indeed well-formed by proving they are equivalent to formulas ◇ Q and Q ⁎ respectively. Further, we generalize ⋁ i ∈ N 0 ◯ i Q to ⋁ i ∈ N 0 P (i) ∧ ◯ i Q and explore the least and greatest fixed-points of an abstract equation X ≡ Q ∨ P ∧ ◯ X. Based on these, some well-formed special instances of ⋁ i ∈ N 0 P (i) ∧ ◯ i Q are obtained. Besides, with the index set expression technique, we equivalently represent ' U ' (strong until) and ' W ' (weak until) constructs of propositional Linear Temporal Logic (LTL) within Propositional Projection Temporal Logic (PPTL). [ABSTRACT FROM AUTHOR]

In this paper, we study the k -forest problem in the model of resource augmentation. In the k -forest problem, given an edge-weighted graph G (V , E) , a parameter k , and a set of m demand pairs ⊆ V × V , the objective is to construct a minimum-cost subgraph that connects at least k demands. The problem is hard to approximate—the best-known approximation ratio is O (min ⁡ { | V | , k }). Furthermore, k -forest is as hard to approximate as the notoriously-hard densest k -subgraph problem. While the k -forest problem is hard to approximate in the worst-case, we show that with the use of resource augmentation, we can efficiently approximate it up to a constant factor. First, we restate the problem in terms of the number of demands that are not connected. In particular, the objective of the k -forest problem can be viewed as to remove at most m − k demands and find a minimum-cost subgraph that connects the remaining demands. We use this perspective of the problem to explain the performance of our algorithm (in terms of the augmentation) in a more intuitive way. Specifically, we present a polynomial-time algorithm for the k -forest problem that, for every ε > 0 , removes at most m − k demands and has cost no more than O (1 / ε 2) times the cost of an optimal algorithm that removes at most (1 − ε) (m − k) demands. [ABSTRACT FROM AUTHOR]

This paper deals with the conversion of expressions denoting Hadamard series into weighted rotating automata. We prove that any algorithm converting rational series into one-way weighted automata can be extended to provide an algorithm which achieves our goal. We apply this to define the derivation and the follow automata of a Hadamard expression. Our method may also be used to extend algorithms which perform the inverse conversion, but it is required to enhance the algorithm to fulfil some constraints. [ABSTRACT FROM AUTHOR]

Abstract: Labelle and Lamathe introduced in 2009 a generalization of the standard combinatorial differential species operator D, by giving a combinatorial interpretation to , where and are two-sort and one-sort species respectively. One can show that such operators can be decomposed as sums of products of simpler operators called atomic combinatorial differential operators. In their paper, Labelle and Lamathe presented a list of the first atomic differential operators. In this paper, we describe an algorithm that allows to generate (and enumerate) all of them, subject to available computer resources. We also give a detailed analysis of how to compute the molecular components of . [Copyright &y& Elsevier]

Abstract: This paper proposes a four dimensional orthogonal packing and time scheduling problem. The problem differs from the classical packing problems in that the position and orientation of each item in the container can be changed over time. In this way, the four dimensional space–time problem better uses the container time. Also, we consider a general case that all parameters are real numbers, which makes the problems more difficult to solve. This paper proposes an algorithm and proves that the algorithm could solve the problem optimally by a finite number of operations. We say this problem is weak computational, meaning that if there exists a universal machine that could represent real numbers and could do unit arithmetic or logical operation on real numbers in finite time, then the algorithm could find optimal solutions in finite time. This paper also presents a proof of the weak computability over a general case of the three dimensional orthogonal packing problem where all parameters are positive real numbers. [Copyright &y& Elsevier]

Abstract: This paper describes the biological and theoretical foundations of a new Artificial Immune System the Receptor Density Algorithm. The algorithm is developed with inspiration from T cell signalling processes and has application in anomaly detection. Connections between the Receptor Density Algorithm and kernel density estimation with exponential smoothing are demonstrated. Finally, the paper evaluates the algorithm’s performance on two types of anomaly detection problem. [Copyright &y& Elsevier]

Abstract: This paper extends a result of Graillat, which was based on Rump’s Theorem, to show that pseudospectra of matrix polynomials expressed in other bases, and also some nonlinear matrix functions, are unaffected by drawing the matrix coefficients from certain structured families. We show by example that this behaviour is not universal. This result is of interest because computation of structured pseudospectra is much more expensive in general than computation of unstructured pseudospectra, and in the cases covered by Rump’s Theorem there is no point going to the extra effort. The paper also contains some examples that may be of interest to the community, including an analytical solution of a nested exponential equation that shows why exponential polynomial decomposition algorithms may be of interest. [Copyright &y& Elsevier]

Abstract: In this paper, we study the geodetic convexity of graphs, focusing on the problem of the complexity of computing a minimum hull set of a graph in several graph classes. For any two vertices of a connected graph , the closed interval of and is the set of vertices that belong to some shortest -path. For any , let . A subset is geodesically convex or convex if . In other words, a subset is convex if, for any and for any shortest -path , . Given a subset , the convex hull of is the smallest convex set that contains . We say that is a hull set of if . The size of a minimum hull set of is the hull number of , denoted by . The Hull Number problem is to decide whether , for a given graph and an integer . Dourado et al. showed that this problem is NP-complete in general graphs. In this paper, we answer an open question of Dourado et al. (2009) [1] by showing that the Hull Number problem is NP-hard even when restricted to the class of bipartite graphs. Then, we design polynomial-time algorithms to solve the Hull Number problem in several graph classes. First, we deal with the class of complements of bipartite graphs. Then, we generalize some results in Araujo et al. (2011) [2] to the class of -graphs and to cacti. Finally, we prove tight upper bounds on the hull numbers. In particular, we show that the hull number of an -node graph without simplicial vertices is at most in general, at most if is regular or has no triangle, and at most if has girth at least . [Copyright &y& Elsevier]

Abstract: Reaction systems are a formal model based on the regulation mechanisms of facilitation and inhibition between biochemical reactions, which underlie the functioning of living cells. The aim of this paper is to explore the expressive power of reaction systems as a modeling framework, showing how their basic assumptions and properties can be exploited to formalize computer science and biology oriented problems. In this view, we first provide a reaction-based description of an iterative algorithm to solve the Tower of Hanoi puzzle. Then, we show how the regulation of gene expression in the lac operon, involved in the metabolism of lactose in Escherichia coli cells, can be formalized in terms of reaction systems. Finally, we present a method to derive, given a reaction system with reactions, a functionally equivalent system with reactions using simplification methods of boolean expressions. Some final remarks and directions for future research conclude the paper. [Copyright &y& Elsevier]

Abstract: In this paper, we consider the model of communication where wireless devices can either switch their radios off to save energy (and hence, can neither send nor receive messages), or switch their radios on and engage in communication. The problem has been extensively studied in practice, in the setting such as deployment and clock synchronization of wireless sensor networks. We distill a clean theoretical formulation of minimizing radio use and present near-optimal solutions. Our base model ignores issues of communication interference, although we also extend the model to handle this requirement. We assume that nodes intend to communicate periodically, or according to some time-based schedule. Clearly, perfectly synchronized devices could switch their radios on for exactly the minimum periods required by their joint schedules. The main challenge in the deployment of wireless networks is to synchronize the devices’ schedules, given that their initial schedules may be offset relative to one another (even if their clocks run at the same speed). In this paper, we study how frequently the devices must switch on their radios in order to both synchronize their clocks and communicate. In this setting, we significantly improve previous results, and show optimal use of the radio for two processors and near-optimal use of the radio for synchronization of an arbitrary number of processors. In particular, for two processors we prove deterministic matching upper and lower bounds on the number of times the radio has to be on, where is the discretized uncertainty period of the clock shift between the two processors. (In contrast, all previous results for two processors are randomized.) For processors (for any positive ) we prove is the lower bound on the number of times the radio has to be switched on (per processor), and show a nearly matching (in terms of the radio use) Õ randomized upper bound per processor. For our algorithm runs with at most poly-log radio invocations per processor. Our bounds also hold in a radio-broadcast model where interference must be taken into account. [Copyright &y& Elsevier]

Abstract: On-line algorithms have been extensively studied for the one-dimensional bin packing problem. In this paper, we investigate two classes of one-dimensional bin packing algorithms, and we give better lower bounds for their asymptotic worst-case behavior. For on-line algorithms so far the best lower bound was given by van Vliet in (1992) . He proved that there is no on-line bin packing algorithm with better asymptotic performance ratio than 1.54014…. In this paper, we give an improvement on this bound to and we investigate the parametric case as well. For those lists where the elements are preprocessed according to their sizes in non-increasing order, Csirik et al. (1983)  proved that no on-line algorithm can have an asymptotic performance ratio smaller than . We improve this result to . [Copyright &y& Elsevier]

Abstract: The utilization of populations is one of the most important features of evolutionary algorithms (EAs). There have been many studies analyzing the impact of different population sizes on the performance of EAs. However, most of such studies are based on computational experiments, except for a few cases. The common wisdom so far appears to be that a large population would increase the population diversity and thus help an EA. Indeed, increasing the population size has been a commonly used strategy in tuning an EA when it did not perform as well as expected for a given problem. He and Yao (2002)  showed theoretically that for some problem instance classes, a population can help to reduce the runtime of an EA from exponential to polynomial time. This paper analyzes the role of population further in EAs and shows rigorously that large populations may not always be useful. Conditions, under which large populations can be harmful, are discussed in this paper. Although the theoretical analysis was carried out on one multimodal problem using a specific type of EAs, it has much wider implications. The analysis has revealed certain problem characteristics, which can be either the problem considered here or other problems, that lead to the disadvantages of large population sizes. The analytical approach developed in this paper can also be applied to analyzing EAs on other problems. [Copyright &y& Elsevier]

Abstract: The advent of high throughput technologies, in particular microarrays, for biological research has revived interest in clustering, resulting in a plethora of new clustering algorithms. However, model selection, i.e., the identification of the correct number of clusters in a dataset, has received relatively little attention. Indeed, although central for statistics, its difficulty is also well known. Fortunately, a few novel techniques for model selection, representing a sharp departure from previous ones in statistics, have been proposed and gained prominence for microarray data analysis. Among those, the stability-based methods are the most robust and best performing in terms of prediction, but the slowest in terms of time. It is very unfortunate that as fascinating and classic an area of statistics as model selection, with important practical applications, has received very little attention in terms of algorithmic design and engineering. In this paper, in order to partially fill this gap, we make the following contributions: (A) the first general algorithmic paradigm for stability-based methods for model selection; (B) reductions showing that all of the known methods in this class are an instance of the proposed paradigm; (C) a novel algorithmic paradigm for the class of stability-based methods for cluster validity, i.e., methods assessing how statistically significant is a given clustering solution; (D) a general algorithmic paradigm that describes heuristic and very effective speed-ups known in the literature for stability-based model selection methods. Since the performance evaluation of model selection algorithms is mainly experimental, we offer, for completeness and without even attempting to be exhaustive, a representative synopsis of known experimental benchmarking results that highlight the ability of stability-based methods for model selection and the computational resources that they require for the task. As a whole, the contributions of this paper generalize in several respects reference methodologies in statistics and show that algorithmic approaches can yield deep methodological insights into this area, in addition to practical computational procedures. [Copyright &y& Elsevier]

Abstract: This paper discusses a model of constraint satisfaction problems known as uniquely extendible constraint satisfaction problems. This model includes and generalizes XOR-SAT, and the model includes an NP-complete problem that appears to share many of the threshold characteristics of random SAT. In this paper we find an exact threshold in the behavior of two versions of DPLL on random instances of this problem. One version uses the unit clause heuristic, and the other uses the generalized unit clause heuristic. Specifically, for DPLL with the unit clause heuristic, we prove that there is a clause density , smaller than the satisfiability threshold, such that for random instances with density smaller than this threshold, DPLL with unit clause will find a satisfying assignment in linear time, with uniformly positive probability. However, for random instances with density larger than this threshold, DPLL with unit clause will require exponential time, with uniformly positive probability, to find a satisfying assignment. We then find the equivalent threshold density for DPLL with the generalized unit clause heuristic. We also prove the analog of the -SAT Conjecture for this class of problems. [Copyright &y& Elsevier]

For the underlying graph G of a network, k (⩾ 2) spanning trees of G are called completely independent spanning trees (CISTs for short) if they are mutually inner-node-disjoint. It is well-known that determining the existence of k CISTs in a graph is an NP-hard problem, even for k = 2. Also, there exists a k -connected graph which does not possess two CISTs for any k ⩾ 2. Accordingly, researches focused on the problem of constructing multiple CISTs in some particular famous networks. Pai and Chang (2016) proposed a unified approach to recursively construct two CISTs with diameter 2 n − 1 in several n -dimensional hypercube-variant networks for n ⩾ 4 , including locally twisted cubes L T Q n and crossed cubes C Q n. Later on, new constructions showed that the diameter of two CISTs can be reduced to 2 n − 2 if n = 4 and 2 n − 3 if n ⩾ 5 for L T Q n , and to 2 n − 2 if n = 4 , 5 and 2 n − 3 if n ⩾ 6 for C Q n. In this paper, we intend to construct more CISTs for those networks that are paid attention. We develop a novel tree searching algorithm, called two-stages tree-searching algorithm (abbreviated as TS 2), which can be used to construct three CISTs of a 6-regular graph if the scale of the graph is not too large and there exist three CISTs for certain. In particular, we demonstrate that three CISTs of L T Q 6 and C Q 6 can be acquired by using TS 2. Moreover, for high-dimensional L T Q n and C Q n with n ⩾ 7 , we show that their three CISTs can be constructed by recursion. Consequently, we obtain the following results: (i) For L T Q n , the diameters of three CISTs we constructed are 11, 12 and 12 when n = 6 , and all are 2 n − 1 when n ⩾ 7 ; (ii) For C Q n , all diameters of three CISTs we constructed are 12 when n = 6 , and 2 n + 1 when n ⩾ 7. [ABSTRACT FROM AUTHOR]

We consider networks of processes which interact with beeps. In the basic model defined by Cornejo and Kuhn [8] , which we refer to as the BL variant, processes can choose in each round either to beep or to listen. Those who beep are unable to detect simultaneous beeps. Those who listen can only distinguish between silence and the presence of at least one beep. Beeping models are weak in essence and even simple tasks may become difficult or unfeasible with them. In this paper, we address the problem of computing how many participants there are in a one-hop network: the counting problem. We first observe that no algorithm can compute this number with certainty in BL , even if it is randomised (Las Vegas). We thus consider the stronger variant where beeping nodes are able to detect simultaneous beeps, referred to as B c d L (cd stands for collision detection). We prove that at least n rounds are necessary in B c d L , and we present an algorithm whose running time is O (n) rounds with high probability. Further experimental results show that its expected running time is less than 10 n. Finally, we discuss how this algorithm can be adapted in other beeping models. In particular, we show that the algorithm can be emulated in BL , at the cost of a logarithmic slowdown and of trading its Las Vegas nature (certain result, uncertain time) against a Monte Carlo one (certain time, uncertain result). [ABSTRACT FROM AUTHOR]