Algorithmic Aspects in Information and Management

We describe and analyze a simple mechanism for the Combinatorial Public Project Problem (Cppp), a prototypical abstract model for decision making by autonomous strategic agents. The problem asks for the selection of k out of m available items, so that the social welfare is maximized. With respect to truthful Mechanism Design, the Cppp has been shown to suffer from limited computationally tractable approximability. Instead, we study a non-truthful Item Bidding mechanism, which elicits the agents’ preferences through separate bids on the items and selects the k items with the highest sums of bids. We pair this outcome determination rule with a payment scheme that determines – for each agent – a separate price for each item in the outcome. For expressive classes of the agents’ valuation functions, we establish existence of welfare-optimal pure Nash equilibria and strong equilibria. Subsequently, we derive worst-case upper and lower bounds on the approximation of the optimal welfare achieved at strong equilibrium, and at (mixed) Bayes-Nash equilibrium, under an incomplete information setting. The mechanism retains good stability properties and favors an advantage compared to recent related approaches, given its simple per-item bidding and pricing rules, and its comparable performance with respect to welfare approximation.

A discrete space-filling curve provides a 1-dimensional indexing or traversal of a multi-dimensional grid space. Applications of space-filling curves include multi-dimensional indexing methods, parallel computing, and image compression. Common goodness-measures for the applicability of space-filling curve families are locality and clustering. Locality reflects proximity preservation that close-by grid points are mapped to close-by indices or vice versa. We present an analytical study on the locality property of the 2-dimensional Hilbert curve family. The underlying locality measure, based on the p-normed metric \(d_{p}\), is the maximum ratio of \(d_{p}(u, v)^{m}\) to \(d_{p}(\tilde{u}, \tilde{v})\) over all corresponding point-pairs (u, v) and \((\tilde{u}, \tilde{v})\) in the m-dimensional grid space and 1-dimensional index space, respectively. Our analytical results identify all candidate representative grid-point pairs (realizing the locality-measure values) for all real norm-parameters in the unit interval [1, 2] and grid-orders. Together with the known results for other norm-parameter values, we have almost complete knowledge of the locality measure of 2-dimensional Hilbert curves over the entire spectrum of possible norm-parameter values.

We study the computational complexity of the problem of computing an optimal clustering \(\{A_1,A_2,...,A_k\}\) of a set of points assuming that every cluster size \(|A_i|\) belongs to a given set M of positive integers. We present a polynomial time algorithm for solving the problem in dimension 1, i.e. when the points are simply rational values, for an arbitrary set M of size constraints, which extends to the \(\ell _1\)-norm an analogous procedure known for the \(\ell _2\)-norm. Moreover, we prove that in the Euclidean plane, i.e. assuming dimension 2 and \(\ell _2\)-norm, the problem is NP-hard even with size constraints set reduced to \(M=\{2,3\}\).

With the increasing impact of genomics in life sciences, the inference of high quality, reliable, and complete genome sequences is becoming critical. Genome assembly remains a major bottleneck in bioinformatics: indeed, high throughput sequencing apparatus yield millions of short sequencing reads that need to be merged based on their overlaps. Overlap graph based algorithms were used with the first generation of sequencers, while de Bruijn graph (DBG) based methods were preferred for the second generation. Because the sequencing coverage varies locally along the molecule, state-of-the-art assembly programs now follow an iterative process that requires the construction of de Bruijn graphs of distinct orders (i.e., sizes of the overlaps). The set of resulting sequences, termed unitigs, provide an important improvement compared to single DBG approaches. Here, we present a novel approach based on a digraph, the Superstring Graph, that captures all desired sizes of overlaps at once and allows to discard unreliable overlaps. With a simple algorithm, the Superstring Graph delivers sequences that includes all the unitigs obtained from multiple DBG as substrings. In linear time and space, it combines the efficiency of a greedy approach to the advantages of using a single graph. In summary, we present a first and formal comparison of the output of state-of-the-art genome assemblers.

In phylogenetics, a central problem is to infer the evolutionary relationships between a set of species X; these relationships are often depicted via a phylogenetic tree – a tree having its leaves univocally labeled by elements of X and without degree-2 nodes – called the “species tree”. One common approach for reconstructing a species tree consists in first constructing several phylogenetic trees from primary data (e.g. DNA sequences originating from some species in X), and then constructing a single phylogenetic tree maximizing the “concordance” with the input trees. The so-obtained tree is our estimation of the species tree and, when the input trees are defined on overlapping – but not identical – sets of labels, is called “supertree”. In this paper, we focus on two problems that are central when combining phylogenetic trees into a supertree: the compatibility and the strict compatibility problems for unrooted phylogenetic trees. These problems are strongly related, respectively, to the notions of “containing as a minor” and “containing as a topological minor” in the graph community. Both problems are known to be fixed-parameter tractable in the number of input trees k, by using their expressibility in Monadic Second Order Logic and a reduction to graphs of bounded treewidth. Motivated by the fact that the dependency on k of these algorithms is prohibitively large, we give the first explicit dynamic programming algorithms for solving these problems, both running in time \(2^{O(k^2)}\,\cdot n\), where n is the total size of the input.

String matching is the problem of finding all the substrings of a text which correspond to a given pattern. It’s one of the most investigated problem in computer science, mainly due to its various applications in many fields. In recent years most solutions to the problem focused on efficiency and flexibility of the searching procedure and effective techniques appeared to speed-up previous solutions. In this paper we present a simple and very efficient algorithm for string matching. It can be seen as an extension of the Skip-Search algorithm to condensed alphabets with the aim of reducing the number of verifications during the searching phase. From our experimental results it turns out that the new variant obtains in most cases the best running time when compared against the most effective algorithms in literature. This makes the new algorithm one of the most flexible solutions in practical cases.

An identifying code in a graph G is a subset of vertices with the property that for each vertex \(v \in V(G)\), the collection of elements of C at distance at most 1 from v is non-empty and distinct from the collection of any other vertex. We consider the minimum density \(d^*(\mathcal{S}_k)\) of an identifying code in the square grid \(\mathcal{S}_k\) of height k (i.e. with vertex set \( \mathbb {Z} \times \{1, \dots , k\}\)). Using the Discharging Method, we prove \(\displaystyle \frac{7}{20} + \frac{1}{20k} \le d^*(\mathcal{S}_k) \le \min \left\{ \frac{2}{5}, \frac{7}{20} + \frac{3}{10k} \right\} \), and \(\displaystyle d^*(\mathcal{S}_3) =\frac{7}{18}\).

This paper studies the problem of traffic monitoring which consists in differentiating a set of walks on a directed graphs by placing sensors on as few arcs as possible. The problem of characterising a set of individuals by testing as few attributes as possible is already well-known but traffic monitoring presents new challenges that the previous models of separation fall short at modelling such as taking into account the multiplicity and order of the arcs in a walk. We therefore introduce a new stronger model of separation based on languages that generalises the traffic monitoring problem. We study two subproblems that we think are especially relevant for practical applications and develop methods to solve them combining integer linear programming, separating codes and language theory.

We consider Persistence, a new online problem concerning optimizing weighted observations in a stream of data when the observer has limited buffer capacity. A stream of weighted items arrive one at a time at the entrance of a buffer with two holding locations. A processor (or observer) can process (observe) an item at the buffer location it chooses, deriving this way the weight of the observed item as profit. The main constraint is that the processor can only move synchronously with the item stream. Persistence is the online problem of scheduling the processor movements through the buffer so that its total derived value is maximized under this constraint. We study the performance of the straight-forward heuristic Threshold, i.e., forcing the processor to “follow” an item through the whole buffer only if its value is above a threshold. We analyze both the optimal offline and Threshold algorithms in the cases where the input stream is either a random permutation, or its items are iid valued. We show that in both cases the competitive ratio achieved by the Threshold algorithm is at least 2/3 when the only statistical knowledge of the items is the median of all possible values. We generalize our results by showing that Threshold, equipped with some minimal statistical advice about the input, achieves competitive ratios in the whole spectrum between 2/3 and 1, following the variation of a newly defined density-like measure of the input. This result is a significant improvement over the case of arbitrary input streams, where we show that no online algorithm can achieve a competitive ratio better than 1/2.

This paper studies Upper Domination, i.e., the problem of computing the maximum cardinality of a minimal dominating set in a graph, with a focus on parameterised complexity. Our main results include W[1]-hardness for Upper Domination, contrasting FPT membership for the parameterised dual Co-Upper Domination. The study of structural properties also yields some insight into Upper Total Domination. We further consider graphs of bounded degree and derive upper and lower bounds for kernelisation.

We consider two variants of the network formation game that aims to capture the impact of selfish behavior, on behalf of the network administrators, on the overall network structure and performance. In particular, we study basic network creation games, where each player aims to minimize her distance to the remaining players, and we present an improved lower bound on the graph diameter of equilibria of this game. We also consider network formation games with a large number of heterogeneous players and monetary transfers, and prove tight bounds on the price of anarchy under realistic assumptions about the cost function. Finally, we argue about the setting where these heterogeneous players must be connected with additional node-disjoint paths to mitigate the impact of failures.

Given a task that requires some skills and a social network of individuals with different skills, the Team Formation problem asks to find a team of individuals that together can perform the task, while minimizing communication costs. Since the problem is NP-hard, we identify the source of intractability by analyzing its parameterized complexity with respect to parameters such as the total number of skills k, the team size l, the communication cost budget b, and the maximum vertex degree \(\varDelta \). We show that the computational complexity strongly depends on the communication cost measure: when using the weight of a minimum spanning tree of the subgraph formed by the selected team, we obtain fixed-parameter tractability for example with respect to the parameter k. In contrast, when using the diameter as measure, the problem is intractable with respect to any single parameter; however, combining \(\varDelta \) with either b or l yields fixed-parameter tractability.

Imagine a disaster in which all edges of a network go down simultaneously. Imagine further that the routing tables of the nodes were not destroyed but are still available. Can one “reconstruct” the network from the routing tables? This question was first asked by Kranakis, Krizanc and Urrutia in 1995 as part of an attempt to answer the question of how much information about the network is stored in the node routing tables. In this paper, we answer this question in the affirmative if the underlying network is a cactus graph by providing an algorithm that returns all node-labelled cacti consistent with a given set of routing tables. This is the first such result for a class of non-geodetic graphs.

A minimum dominating set (MDS) of a simple undirected graph G is a dominating set with the smallest possible cardinality among all dominating sets of G and the MDS problem represents the problem of finding the MDS in a given input graph.

Motivated by the transportation, social and biological networks from a control theory perspective, the main result of this paper is the assertion that a random sampling is usable to find a near-optimal dominating set in an arbitrary connected graph. Our result might be of significance in particular contexts where exact algorithms cannot be run, e.g. in distributed computation environments. Moreover, the analysis of the relationship between the time complexity and the approximation ratio of the corresponding sequential algorithm exposes the counterintuitive behavior.

In recent years, several combinatorial problems were introduced in the area of access control. Typically, such problems deal with an authorization policy, seen as a relation \( UR \subseteq U\times R\), where \((u, r) \in UR \) means that user u is authorized to access resource r. Li, Tripunitara and Wang (2009) introduced the Resiliency Checking Problem (RCP), in which we are given an authorization policy, a subset of resources \(P \subseteq R\), as well as integers \(s \ge 0\), \(d \ge 1\) and \(t \ge 1\). It asks whether upon removal of any set of at most s users, there still exist d pairwise disjoint sets of at most t users such that each set has collectively access to all resources in P. This problem possesses several parameters which appear to take small values in practice. We thus analyze the parameterized complexity of RCP with respect to these parameters, by considering all possible combinations of |P|, s, d, t. In all but one case, we are able to settle whether the problem is in FPT, XP, W[2]-hard, para-NP-hard or para-coNP-hard. We also consider the restricted case where \(s=0\) for which we determine the complexity for all possible combinations of the parameters.

Given a pattern x of length m and a text y of length n, both over an ordered alphabet, the order-preserving pattern matching problem consists in finding all substrings of the text with the same relative order as the pattern. The OPPM, which might be viewed as an approximate variant of the well known exact pattern matching problem, has gained attention in recent years. This interesting problem finds applications in a lot of fields as from time series analysis, like share prices on stock markets or weather data analysis, to musical melody matching. In this paper we present two new filtering approaches which turn out to be much more effective in practice than the previously presented methods by reducing the number of false positives up to 99 %. From our experimental results it turns out that our proposed solutions are up to 2 times faster than the previous solutions.

In this paper, we study the line-constrained k-center problem in the Euclidean plane. Given a set of demand points and a line L, the problem asks for k points, called center facilities, on L, such that the maximum of the distances from the demand points to their closest center facilities is minimized. For any fixed k, we propose an algorithm with running time linear to the number of demand points.

This work focuses on a special case of the secretary problem: only a few applicants have access to the interview, and they belong to some class of people (e.g., bachelors, undergraduates or veterans). The overall ability of the applicants is known to the interviewer. This domain occurs when the positions require high professional skills (e.g., pilots, doctors or musicians). This work considers an extension of the classical k-max search model [1, 15] to approach this domain. In the new model, we design a case in which the pool of applicants is not large, and introduced the parameter \(\bar{S}\) to measure the overall ability of the applicants. First, we modify the threat based policy (TBP) algorithm [6], and obtain a new algorithm-TBPS. We prove that TBPS outperforms the optimal k-max search algorithm (KMS) [15] in the new model. Second, we modify KMS and obtain a new algorithm: Modified k-max search algorithm (MKMS). We prove that MKMS outperforms KMS in the new model without respecting to the value of \(\bar{S}\). Finally, numerical results are presented to demonstrate the performance of MKMS and TBPS.