Fixed-Parameter Complexity of Minimum Profile Problems

The profile of a graph is an integer-valued parameter defined via vertex orderings; it is known that the profile of a graph equals the smallest number of edges of an interval supergraph. Since computing the profile of a graph is an NP-hard problem, we consider parameterized versions of the problem. Namely, we study the problem of deciding whether the profile of a connected graph of order n is at most n−1+k, considering k as the parameter; this is a parameterization above guaranteed value, since n−1 is a tight lower bound for the profile. We present two fixed-parameter algorithms for this problem. The first algorithm is based on a forbidden subgraph characterization of interval graphs. The second algorithm is based on two simple kernelization rules which allow us to produce a kernel with linear number of vertices and edges. For showing the correctness of the second algorithm we need to establish structural properties of graphs with small profile which are of independent interest. A preliminary version of the paper is published in Proc. IWPEC 2006, LNCS vol. 4169, 60–71.     

An Improved (and Practical) Parameterized Algorithm for the Individual Haplotyping Problem MFR with Mate-Pairs

The Individual Haplotyping MFR problem is a computational problem that, given a set of DNA sequence fragment data of an individual, induces the corresponding haplotypes by dropping the minimum number of fragments. Bafna, Istrail, Lancia, and Rizzi proposed an algorithm of time O(2^2k m ² n+2^3k m ³) for the problem, where m is the number of fragments, n is the number of SNP sites, and k is the maximum number of holes in a fragment. When there are mate-pairs in the input data, the parameter k can be as large as 100, which would make the Bafna-Istrail-Lancia-Rizzi algorithm impracticable. The current paper introduces a new algorithm PM-MFR of running time , where k ₁ is the maximum number of SNP sites that a fragment covers (k ₁ is smaller than n), and k ₂ is the maximum number of fragments that cover a SNP site (k ₂ is usually about 10). Since the time complexity of the algorithm PM-MFR is not directly related to the parameter k, the algorithm solves the Individual Haplotyping MFR problem with mate-pairs more efficiently and is more practical in real biological applications. This research was supported in part by the National Natural Science Foundation of China under Grant Nos. 60433020 and 60773111, the Program for New Century Excellent Talents in University No. NCET-05-0683, the Program for Changjiang Scholars and Innovative Research Team in University No. IRT0661, and the Scientific Research Fund of Hunan Provincial Education Department under Grant No. 06C526.     

Grouping Techniques for Scheduling Problems: Simpler and Faster

In this paper we describe a general grouping technique to devise faster and simpler approximation schemes for several scheduling problems. We illustrate the technique on two different scheduling problems: scheduling on unrelated parallel machines with costs and the job shop scheduling problem. The time complexity of the resulting approximation schemes is always linear in the number n of jobs, and the multiplicative constant hidden in the O(n) running time is reasonably small and independent of the error ε. Supported by Swiss National Science Foundation project 200020-109854, “Approximation Algorithms for Machine scheduling Through Theory and Experiments II”. A preliminary version of this paper appeared in the Proceedings of ESA’01.     

A hybrid aggregation and compression technique for road network databases

Vector data and in particular road networks are being queried, hosted and processed in many application domains such as in mobile computing. Many client systems such as PDAs would prefer to receive the query results in unrasterized format without introducing an overhead on overall system performance and result size. While several general vector data compression schemes have been studied by different communities, we propose a novel approach in vector data compression which is easily integrated within a geospatial query processing system. It uses line aggregation to reduce the number of relevant tuples and Huffman compression to achieve a multi-resolution compressed representation of a road network database. Our experiments performed on an end-to-end prototype verify that our approach exhibits fast query processing on both client and server sides as well as high compression ratio.

Random Bichromatic Matchings

Given a graph with edges colored Red and Blue, we study the problem of sampling and approximately counting the number of matchings with exactly k Red edges. We solve the problem of estimating the number of perfect matchings with exactly k Red edges for dense graphs. We study a Markov chain on the space of all matchings of a graph that favors matchings with k Red edges. We show that it is rapidly mixing using non-traditional canonical paths that can backtrack. We show that this chain can be used to sample matchings in the 2-dimensional toroidal lattice of any fixed size ℓ with k Red edges, where the horizontal edges are Red and the vertical edges are Blue. An extended abstract appeared in J.R. Correa, A. Hevia and M.A. Kiwi (eds.) Proceedings of the 7th Latin American Theoretical Informatics Symposium, LNCS 3887, pp. 190–201, Springer, 2006. N. Bhatnagar’s and D. Randall’s research was supported in part by NSF grants CCR-0515105 and DMS-0505505. V.V. Vazirani’s research was supported in part by NSF grants 0311541, 0220343 and CCR-0515186. N. Bhatnagar’s and E. Vigoda’s research was supported in part by NSF grant CCR-0455666.     

Instance weighting versus threshold adjusting for cost-sensitive classification

In real-world classification problems, different types of misclassification errors often have asymmetric costs, thus demanding cost-sensitive learning methods that attempt to minimize average misclassification cost rather than plain error rate. Instance weighting and post hoc threshold adjusting are two major approaches to cost-sensitive classifier learning. This paper compares the effects of these two approaches on several standard, off-the-shelf classification methods. The comparison indicates that the two approaches lead to similar results for some classification methods, such as Naïve Bayes, logistic regression, and backpropagation neural network, but very different results for other methods, such as decision tree, decision table, and decision rule learners. The findings from this research have important implications on the selection of the cost-sensitive classifier learning approach as well as on the interpretation of a recently published finding about the relative performance of Naïve Bayes and decision trees.     

Algorithms for unimodal segmentation with applications to unimodality detection

We study the problem of segmenting a sequence into k pieces so that the resulting segmentation satisfies monotonicity or unimodality constraints. Unimodal functions can be used to model phenomena in which a measured variable first increases to a certain level and then decreases. We combine a well-known unimodal regression algorithm with a simple dynamic-programming approach to obtain an optimal quadratic-time algorithm for the problem of unimodal k-segmentation. In addition, we describe a more efficient greedy-merging heuristic that is experimentally shown to give solutions very close to the optimal. As a concrete application of our algorithms, we describe methods for testing if a sequence behaves unimodally or not. The methods include segmentation error comparisons, permutation testing, and a BIC-based scoring scheme. Our experimental evaluation shows that our algorithms and the proposed unimodality tests give very intuitive results, for both real-valued and binary data. Niina Haiminen received the M.Sc. degree from the University of Helsinki in 2004. She is currently a Graduate Student at the Department of Computer Science of University of Helsinki, and a Researcher at the Basic Research Unit of Helsinki Institute for Information Technology. Her research interests include algorithms, bioinformatics, and data mining. Aristides Gionis received the Ph.D. degree from Stanford University in 2003, and he is currently a Senior Researcher at the Basic Research Unit of Helsinki Institute for Information Technology. His research experience includes summer internship positions at Bell Labs, AT&T Labs, and Microsoft Research. His research areas are data mining, algorithms, and databases. Kari Laasonen received the M.Sc. degree in Theoretical Physics in 1995 from the University of Helsinki. He is currently a Graduate Student in Computer Science at the University of Helsinki and a Researcher at the Basic Research Unit of Helsinki Institute for Information Technology. His research is focused on algorithms and data analysis methods for pervasive computing.     

A framework for simulating real-time multi-agent systems

In this paper, we describe an implementation of use in demonstrating the effectiveness of architectures for real-time multi-agent systems. The implementation provides a simulation of a simplified RoboCup Search and Rescue environment, with unexpected events, and includes a simulator for both a real-time operating system and a CPU. We present experimental evidence to demonstrate the benefit of the implementation in the context of a particular hybrid architecture for multi-agent systems that allows certain agents to remain fully autonomous, while others are fully controlled by a coordinating agent. In addition, we discuss the value of the implementation for testing any models for the construction of real-time multi-agent systems and include a comparison to related work.

Konzeptuelle Modellierung von Geodiensten

Zusammenfassung  Navigationssysteme, ortsbezogene Suchdienste wie Google Maps, interaktive Augmented-Reality-Spiele, Handy-basierte FindMe-Dienste – diese wenige Beispiele zeigen bereits, wie direkt oder indirekt raumbezogene Dienste unser Alltagsleben immer mehr durchdringen. Wir beobachten, wie sich die Nutzung von Geodaten schrittweise vom pers?nlichen Desktop-Geoinformationssystem (GIS) über hausinternen Zugriff auf die Geodatenbank bis zum Webzugriff durch Clients und Servern unterschiedlicher Provenienz ausweitet (,,Web-GIS“). Klassische Aufgaben wie Kartenproduktion und Beauskunftung treten dabei gegenüber komplexen, situationsbezogenen Verknüpfungen von Geo- mit anderen Daten eher in den Hintergrund. Damit geht offensichtlich ein Paradigmenwechsel von der einfachen, passiven Geodatenbereitstellung via WWW zu funktional komplexeren Geodiensten einher. Sollen solche Mehrwertdienste offen und flexibel orchestrierbar sein, so müssen Geodaten systemübergreifend ad hoc abgefragt werden k?nnen. Unabdingbar sind dafür offene Standards, nicht nur auf der Ebene von Datenaustauschformaten, sondern auch bei den Zugriffsdiensten; diese Geoservice-Standardisierung leistet das Open GeoSpatial Consortium (OGC). Im vorliegenden Beitrag geben wir einen überblick über die Modellierung von Web-basierten Geodiensten auf Basis ausgew?hlter OGC-Standards. Modellierung bedeutet in diesem Kontext die Gestaltung von Funktionalit?t und Schnittstellen eines potenziell komplexen Dienstes auf Basis offener Standards und ihrer Basisdienste und -operationen. Diskutiert werden Standards für den Meta-, Vektor- und Rasterdatenzugriff sowie ein anwendungsorientierter Standard für Sensordaten.