Local edge colouring of Yao-like subgraphs of Unit Disk Graphs

The focus of the present paper is on providing a local deterministic algorithm for colouring the edges of Yao-like   subgraphs of Unit Disk Graphs. These are geometric graphs such that for some positive integers l,k$l,k$ the following property holds at each node v$v$: if we partition the unit circle centered at v$v$ into 2k$2k$ equally sized wedges then each wedge can contain at most l$l$ points different from v$v$. We assume that the nodes are location aware, i.e. they know their Cartesian coordinates in the plane. The algorithm presented is local in the sense that each node can receive information emanating only from nodes which are at most a constant (depending on k$k$ and l$l$, but not on the size of the graph) number of hops (measured in the original underlying Unit Disk Graph) away from it, and hence the algorithm terminates in a constant number of steps. The number of colours used is 2kl+1$2kl+1$ and this is optimal for local algorithms (since the maximal degree is 2kl$2kl$ and a colouring with 2kl$2kl$ colours can only be constructed by a global algorithm), thus showing that in this class of graphs the price for locality is only one additional colour.     

Multicriteria 0-1 knapsack problems with k-min objectives

This paper deals with the multicriteria 0-1 knapsack problem (KP) with k$k$-min objectives (MkMIN-KP) in which the first objective is of classical sum type and the remaining objectives are k$k$-min objective functions. The k$k$-min objectives are ordinal objectives, aiming at the maximization of the k$k$ th smallest objective coefficient in any feasible knapsack solution with at least k$k$ items in the knapsack. We develop efficient algorithms for the determination of the complete nondominated set of MkMIN-KP.     

A parameterized view on matroid optimization problems

Matroid theory gives us powerful techniques for understanding combinatorial optimization problems and for designing polynomial-time algorithms. However, several natural matroid problems, such as 3-matroid intersection, are NP-hard. Here we investigate these problems from the parameterized complexity point of view: instead of the trivial n^O(k)$n^{O\left(k\right)}$ time brute force algorithm for finding a k$k$-element solution, we try to give algorithms with uniformly polynomial (i.e., f(k)⋅n^O(1)$f\left(k\right)\cdot n^{O\left(1\right)}$) running time. The main result is that if the ground set of a represented linear matroid is partitioned into blocks of size ?$?$, then we can determine in randomized time f(k,?)⋅n^O(1)$f(k,?)\cdot n^{O\left(1\right)}$ whether there is an independent set that is the union of k$k$ blocks. As a consequence, algorithms with similar running time are obtained for other problems such as finding a k$k$-element set in the intersection of ?$?$ matroids, or finding k$k$ terminals in a network such that each of them can be connected simultaneously to the source by ?$?$ disjoint paths.     

Efficient detection of a locally stable predicate in a distributed system

We present an efficient approach to detect a locally stable predicate in a distributed computation. Examples of properties that can be formulated as locally stable predicates include termination and deadlock of a subset of processes. Our algorithm does not require application messages to be modified to carry control information (e.g., vector timestamps), nor does it inhibit events (or actions) of the underlying computation. The worst-case message complexity of our algorithm is O(n(m+1))$O(n(m+1))$, where n$n$ is the number of processes in the system and m$m$ is the number of events executed by the underlying computation. We show that, in practice, its message complexity should be much lower than its worst-case message complexity. The detection latency of our algorithm is O(d)$O(d)$ time units, where d$d$ is the diameter of communication topology. Our approach also unifies several known algorithms for detecting termination and deadlock. We also show that our algorithm for detecting a locally stable predicate can be used to efficiently detect a stable predicate that is a monotonic function of other locally stable predicates.     

Compatibility of unrooted phylogenetic trees is FPT

A collection of _T1,_T2,…,_Tk$T_1,T_2,\dots ,T_k$ of unrooted, leaf labelled (phylogenetic) trees, all with different leaf sets, is said to be compatible   if there exists a tree T$T$ such that each tree _Ti$T_i$ can be obtained from T$T$ by deleting leaves and contracting edges. Determining compatibility is NP-hard, and the fastest algorithm to date has worst case complexity of around Ω(n^k)$\mathrm{\Omega }(n^k)$ time, n$n$ being the number of leaves. Here, we present an O(nf(k))$\mathrm{O}(\mathit{nf}(k))$ algorithm, proving that compatibility of unrooted phylogenetic trees is fixed parameter tractable   (FPT) with respect to the number k$k$ of trees.     

On semimeasures predicting Martin-Löf random sequences

Solomonoff’s central result on induction is that the prediction of a universal semimeasure M$M$ converges rapidly and with probability 1 to the true sequence generating predictor μ$\mu$, if the latter is computable. Hence, M$M$ is eligible as a universal sequence predictor in the case of unknown μ$\mu$. Despite some nearby results and proofs in the literature, the stronger result of convergence for all (Martin-Löf) random sequences remained open. Such a convergence result would be particularly interesting and natural, since randomness can be defined in terms of M$M$ itself. We show that there are universal semimeasures M$M$ which do not converge to μ$\mu$ on all μ$\mu$-random sequences, i.e. we give a partial negative answer to the open problem. We also provide a positive answer for some non-universal semimeasures. We define the incomputable measure D$D$ as a mixture over all computable measures and the enumerable semimeasure W$W$ as a mixture over all enumerable nearly measures. We show that W$W$ converges to D$D$ and D$D$ to μ$\mu$ on all random sequences. The Hellinger distance measuring closeness of two distributions plays a central role.     

Self-deployment of mobile sensors on a ring

Mobile sensors can self-deploy in a purely decentralized and distributed fashion, so as to reach in a finite time a state of static equilibrium in which they uniformly cover the environment. We consider the self-deployment problem in a ring (e.g., a circular rim); in particular we investigate under what conditions the problem is solvable by a collection of identical sensors without a global coordinate system, however capable of determining the location (in their local coordinate system) of the other sensors within a fixed distance (called visibility radius). A self-deployment is exact   if within finite time the distance between any two consecutive sensors along the ring is the same, d$d$; it is ?$?$-approximate   if within finite time the distance between two consecutive sensors is between d−?$d-?$ and d+?$d+?$.     

Drawing slicing graphs with face areas

We consider orthogonal drawings of a plane graph G$G$ with specified face areas. For a natural number k$k$, a k$k$-gonal drawing of G$G$ is an orthogonal drawing such that the boundary of G$G$ is drawn as a rectangle and each inner face is drawn as a polygon with at most k$k$ corners whose area is equal to the specified value. In this paper, we show that every slicing graph G$G$ with a slicing tree T$T$ and a set of specified face areas admits a 10-gonal drawing D$D$ such that the boundary of each slicing subgraph that appears in T$T$ is also drawn as a polygon with at most 10 corners. Such a drawing D$D$ can be found in linear time.     

Detecting real singularities of a space curve from a real rational parametrization

In this paper we give an algorithm that detects real singularities, including singularities at infinity, and counts local branches and multiplicities of real rational curves in the affine n$n$-space without knowing an implicitization. The main idea behind this is a generalization of the D$D$-resultant (see [van den Essen, A., Yu, J.-T., 1997. The D$D$-resultant, singularities and the degree of unfaithfulness. Proc. Amer. Math. Soc. 25 (3), 689–695]) to n$n$ rational functions. This allows us to find all real parameters corresponding to the real singularities between the solutions of a system of polynomials in one variable.     

Non-reducible descriptions for conditional Kolmogorov complexity

Assume that a program p$p$ on input a$a$ outputs b$b$. We are looking for a shorter program q$q$ having the same property (q(a)=b$q\left(a\right)=b$). In addition, we want q$q$ to be simple conditional to p$p$ (this means that the conditional Kolmogorov complexity K(q|p)$K\left(q\right|p)$ is negligible). In the present paper, we prove that sometimes there is no such program q$q$, even in the case when the complexity of p$p$ is much bigger than K(b|a)$K\left(b\right|a)$. We give three different constructions that use the game approach, probabilistic arguments and algebraic arguments, respectively.     

An equation-based Heap Sizing Rule

For garbage-collected applications, dynamically-allocated objects are contained in a heap. Programmer productivity improves significantly if there is a garbage collector to automatically deallocate objects that are no longer needed by the applications. However, there is a run-time performance overhead in garbage collection, and this cost is sensitive to heap size H$H$: a smaller H$H$ will trigger more collection, but a large H$H$ can cause page faults, as when H$H$ exceeds the size M$M$ of main memory allocated to the application.     

Origami fold as algebraic graph rewriting

We formalize paper fold (origami) by graph rewriting. Origami construction is abstractly described by a rewriting system (O,?)$(\mathbb{O},?)$, where O$\mathbb{O}$ is the set of abstract origamis and ?$?$ is a binary relation on O$\mathbb{O}$, that models fold  . An abstract origami is a structure (Π,∽,?)$(\Pi ,\backsim ,?)$, where Π$\Pi$ is a set of faces constituting an origami, and ∽$\backsim$ and ?$?$ are binary relations on Π$\Pi$, each representing adjacency and superposition relations between the faces.     

A linear-time 2-approximation algorithm for the watchman route problem for simple polygons

Given a simple polygon P$P$ of n$n$ vertices, the watchman route problem   asks for a shortest (closed) route inside P$P$ such that each point in the interior of P$P$ can be seen from at least one point along the route. In this paper, we present a simple, linear-time algorithm for computing a watchman route of length at most two times that of the shortest watchman route. The best known algorithm for computing a shortest watchman route takes O(n⁴logn)$O(n^{4}logn)$ time, which is too complicated to be suitable in practice.     

Finding non-dominated solutions in bi-objective integer network flow problems

This paper deals with an algorithm for finding all the non-dominated solutions and corresponding efficient solutions for bi-objective integer network flow problems. The algorithm solves a sequence of ?$?$-constraint problems and computes all the non-dominated solutions by decreasing order of one of the objective functions. The optimal integer solutions for the ?$?$-constraint problems are determined by exploring a branch-and-bound tree. The algorithm makes use of the network structure to perform the computations, i.e., the network structure of the problem is not destroyed with the inclusion of an ?$?$-constraint. This paper presents the main features of the algorithm, the theoretical bases of the proposed approach and some computational issues. Experiments were done and the results are also reported in the paper.     

On the parameterized complexity of multiple-interval graph problems

Multiple-interval graphs are a natural generalization of interval graphs where each vertex may have more than one interval associated with it. Many applications of interval graphs also generalize to multiple-interval graphs, often allowing for more robustness in the modeling of the specific application. With this motivation in mind, a recent systematic study of optimization problems in multiple-interval graphs was initiated. In this sequel, we study multiple-interval graph problems from the perspective of parameterized complexity. The problems under consideration are k$k$-Independent Set, k$k$-Dominating Set, and k$k$-Clique, which are all known to be W[1]-hard for general graphs, and NP-complete for multiple-interval graphs. We prove that k$k$-Clique is in FPT, while k$k$-Independent Set and k$k$-Dominating Set are both W[1]-hard. We also prove that k$k$-Independent Dominating Set, a hybrid of the two above problems, is also W[1]-hard. Our hardness results hold even when each vertex is associated with at most two intervals, and all intervals have unit length. Furthermore, as an interesting byproduct of our hardness results, we develop a useful technique for showing W[1]-hardness via a reduction from the k$k$-Multicolored Clique problem, a variant of k$k$-Clique. We believe this technique has interest in its own right, as it should help in simplifying W[1]-hardness results which are notoriously hard to construct and technically tedious.     

A new variance-based global sensitivity analysis technique

A new set of variance-based sensitivity indices, called W$W$-indices, is proposed. Similar to the Sobol’s indices, both main and total effect indices are defined. The W$W$-main effect indices measure the average reduction of model output variance when the ranges of a set of inputs are reduced, and the total effect indices quantify the average residual variance when the ranges of the remaining inputs are reduced. Geometrical interpretations show that the W$W$-indices gather the full information of the variance ratio function, whereas, Sobol’s indices only reflect the marginal information. Then the double-loop-repeated-set Monte Carlo (MC) (denoted as DLRS MC) procedure, the double-loop-single-set MC (denoted as DLSS MC) procedure and the model emulation procedure are introduced for estimating the W$W$-indices. It is shown that the DLRS MC procedure is suitable for computing all the W$W$-indices despite its highly computational cost. The DLSS MC procedure is computationally efficient, however, it is only applicable for computing low order indices. The model emulation is able to estimate all the W$W$-indices with low computational cost as long as the model behavior is correctly captured by the emulator. The Ishigami function, a modified Sobol’s function and two engineering models are utilized for comparing the W$W$- and Sobol’s indices and verifying the efficiency and convergence of the three numerical methods. Results show that, for even an additive model, the W$W$-total effect index of one input may be significantly larger than its W$W$-main effect index. This indicates that there may exist interaction effects among the inputs of an additive model when their distribution ranges are reduced.     

From Nerode’s congruence to suffix automata with mismatches

In this paper we focus on the minimal deterministic finite automaton _Sk$S_k$ that recognizes the set of suffixes of a word w$w$ up to k$k$ errors. As first result we give a characterization of the Nerode’s right-invariant congruence that is associated with _Sk$S_k$. This result generalizes the classical characterization described in [A. Blumer, J. Blumer, D. Haussler, A. Ehrenfeucht, M. Chen, J. Seiferas, The smallest automaton recognizing the subwords of a text, Theoretical Computer Science, 40, 1985, 31–55]. As second result we present an algorithm that makes use of _Sk$S_k$ to accept in an efficient way the language of all suffixes of w$w$ up to k$k$ errors in every window of size r$r$ of a text, where r$r$ is the repetition index of w$w$. Moreover, we give some experimental results on some well-known words, like prefixes of Fibonacci and Thue-Morse words. Finally, we state a conjecture and an open problem on the size and the construction of the suffix automaton with mismatches.