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.     

,,Location-based Services“ – Personalisierung mobiler Dienste durch Verortung

Zusammenfassung Im Zeitalter der Informationsgesellschaft, so wurde postuliert, spielten r?umliche Distanzen keine Rolle mehr und unsere r?umliche Mobilit?t n?hme ab. Die Mobilit?t in den letzten Jahren, speziell die Freizeitmobilit?t, hat hingegen zugenommen. Die Bereitstellung ortsbezogener Dienste – ,,Location-based Services“ – unterstützt und f?rdert dieses Verhalten.     

Efficient product sampling using hierarchical thresholding

We present an efficient method for importance sampling the product of multiple functions. Our algorithm computes a quick approximation of the product on the fly, based on hierarchical representations of the local maxima and averages of the individual terms. Samples are generated by exploiting the hierarchical properties of many low-discrepancy sequences, and thresholded against the estimated product. We evaluate direct illumination by sampling the triple product of environment map lighting, surface reflectance, and a visibility function estimated per pixel. Our results show considerable noise reduction compared to existing state-of-the-art methods using only the product of lighting and BRDF.