TY - JOUR
AB - Computing a maximum weighted stable set in a bipartite graph is considered well-solved and usually approached with preflow-push, Ford–Fulkerson or network simplex algorithms. We present a combinatorial algorithm for the problem that is not based on flows. Numerical tests suggest that this algorithm performs quite well in practice and is competitive with flow based algorithms especially in the case of dense graphs.
AU - Faigle, Ulrich
AU - Frahling, Gereon
ID - 23881
JF - Discrete Applied Mathematics
SN - 0166-218X
TI - A combinatorial algorithm for weighted stable sets in bipartite graphs
ER -
TY - CONF
AU - Bennedsen, Jens
AU - Schulte, Carsten
ID - 15697
T2 - PPIG
TI - A Competence Model for Object-Interaction in Introductory Programming
ER -
TY - CONF
AU - Domik, Gitta
ID - 16878
TI - A Computer Graphics Curriculum at the University of Paderborn
ER -
TY - JOUR
AU - Gambuzza, Alfonso
AU - Koert, Dirk
ID - 23294
JF - Postworkshop Proceedings of the 3rd Workshop on Object-oriented Modeling of Embedded Real-Time Systems (OMER3)
TI - A Concept for a Platform-Independent Modelling of Mechatronic Systems: Improving the Re-usability of Models in the Mechatronic Design Process
ER -
TY - JOUR
AU - Carlson, E.
AU - Prehofer, Christian
AU - Bettstetter, Christian
AU - Karl, Holger
AU - Wolisz, Adam
ID - 839
IS - 11
JF - IEEE Journal on Selected Areas in Communications
TI - A Distributed End-to-End Reservation Protocol for IEEE 802.11-Based Wireless Mesh Networks
ER -
TY - CONF
AB - In this paper, we present a randomized constant factor approximation
algorithm for the metric minimum facility location problem with uniform
costs and demands in a distributed setting, in which every point can
open a facility. In particular, our distributed algorithm uses three
communication rounds with message sizes bounded to O(log n) bits where
n is the number of points. We also extend our algorithm to constant
powers of metric spaces, where we also obtain a randomized constant
factor approximation algorithm.
AU - Sohler, Christian
AU - Gehweiler, Joachim
AU - Lammersen, Christiane
ID - 18746
T2 - Proceeedings of 18th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)
TI - A Distributed O(1)-Approximation Algorithm for the Uniform Facility Location Problem
ER -
TY - CONF
AB - In this paper we develop an efficient implementation for a k-means clustering algorithm. Our algorithm is a variant of KMHybrid [28, 20], i.e. it uses a combination of Lloyd-steps and random swaps, but as a novel feature it uses coresets to speed up the algorithm. A coreset is a small weighted set of points that approximates the original point set with respect to the considered problem. The main strength of the algorithm is that it can quickly determine clusterings of the same point set for many values of k. This is necessary in many applications, since, typically, one does not know a good value for k in advance. Once we have clusterings for many different values of k we can determine a good choice of k using a quality measure of clusterings that is independent of k, for example the average silhouette coefficient. The average silhouette coefficient can be approximated using coresets.To evaluate the performance of our algorithm we compare it with algorithm KMHybrid [28] on typical 3D data sets for an image compression application and on artificially created instances. Our data sets consist of 300,000 to 4.9 million points. We show that our algorithm significantly outperforms KMHybrid on most of these input instances. Additionally, the quality of the solutions computed by our algorithm deviates less than that of KMHybrid.We also computed clusterings and approximate average silhouette coefficient for k=1,…,100 for our input instances and discuss the performance of our algorithm in detail.
AU - Frahling, Gereon
AU - Sohler, Christian
ID - 23882
T2 - Proceedings of the twenty-second annual symposium on Computational geometry - SCG '06
TI - A fast k-means implementation using coresets
ER -
TY - CONF
AB - Spam e-mails have become a serious technological and economic problem. So far we have been reasonably able to resist spam e-mails and use the Internet for regular communication by deploying complementary anti-spam approaches. However, if we are to avert the danger of losing the Internet email service as a valuable, free, and worldwide medium of open communication, anti-spam activities should be performed more systematically than is done in current, mainly heuristic, anti-spam approaches. A formal framework within which the modes of spam delivery, anti-spam approaches, and their effectiveness can be investigated, may encourage a shift in methodology and pave the way for new, holistic anti-spam approaches. This paper presents a model of the Internet e-mail infrastructure as a directed graph and a deterministic finite automaton, and draws on automata theory to formally derive the modes of spam delivery possible. Finally the effectiveness of anti-spam approaches in terms of coverage of spamming modes is assessed.
AU - Schryen, Guido
ID - 5659
T2 - 39th Annual Hawaii International Conference on System Sciences
TI - A formal approach towards assessing the effectiveness of anti-spam procedures
ER -
TY - JOUR
AU - Karimi, I.
AU - Hüllermeier, Eyke
AU - Meskouris, K.
ID - 16195
IS - 3
JF - Soft Computing
TI - A fuzzy-probablistic earthquake risk assessment system
VL - 11
ER -
TY - THES
AU - Shen, Qing
ID - 25543
TI - A Method for Composing Virtual Prototypes of Mechatronic Systems in Virtual Environments
VL - 193
ER -
TY - JOUR
AU - Tönnies, Merle
ID - 7616
JF - Stauffenburg Handbücher
TI - A Midsummer Night's Dream
VL - 9
ER -
TY - CONF
AU - Förster, Alexander
AU - Schattkowsky, Tim
AU - Engels, Gregor
AU - Van Der Straeten, Ragnhild
ID - 7955
T2 - IEEE Symposium on Visual Languages and Human-Centric Computing (VL/HCC 2006), Brighton (UK)
TI - A Pattern-driven Development Process for Quality Standard-conforming Business Process Models
ER -
TY - JOUR
AU - Hoene, Christian
AU - Karl, Holger
AU - Wolisz, Adam
ID - 837
IS - 3
JF - Int. J. Communication Systems
TI - A perceptual quality model intended for adaptive VoIP applications
ER -
TY - CONF
AB - In this paper we present the design of a particle filter for post filtering instantaneous positioning estimates of GSM mobile terminals. The instantaneous estimates are obtained by comparing signal power levels, which are reported by the mobile terminal to the base station, with a database of predictions using a novel statistically motivated similarity measure. Unlike a simple Euclidian distance measure, the proposed scheme incorporates inherent information about signal power level measurements requested by the serving base station but not reported by the mobile terminal. Furthermore, we show how the Monte Carlo method of particle filtering helps to obtain better position estimates and, surprisingly, also helps to reduce the computational complexity. Results are presented for real field data.
AU - Peschke, Sven
AU - Haeb-Umbach, Reinhold
ID - 11884
T2 - European Navigation Conference \& Exhibition (ENC 2006)
TI - A Probabilistic Similarity Measure and a Non-Linear Post-Filter for Mobile Phone Positioning using GSM Signal Power Measurements
ER -
TY - CONF
AU - Giese, Holger
AU - Meyer, Matthias
AU - Wagner, Robert
ID - 20951
T2 - Proc. of the 4th International Fujaba Days 2006, Bayreuth, Germany
TI - A Prototype for Guideline Checking and Model Transformation in Matlab/Simulink
VL - tr-ri-06-275
ER -
TY - JOUR
AU - Dubois, D.
AU - Hüllermeier, Eyke
AU - Prade, H.
ID - 16173
IS - 2
JF - Data Mining and Knowledge Discovery
TI - A systematic approach to the assessment of fuzzy association rules
VL - 13
ER -
TY - CONF
AU - Brinker, K.
AU - Fuernkranz, J.
AU - Hüllermeier, Eyke
ED - Brewka, G.
ED - Coradeschi, S.
ED - Perini, A.
ED - Traverso, P.
ID - 14838
T2 - In Proceedings ECAI-2006, 17th European Conference on Artificial Inteligence, Riva del Garda, Italy
TI - A unified model for multilabel classification and ranking
ER -
TY - CONF
AB - We present a web computing library (PUBWCL) in Java that allows to execute tightly coupled, massively parallel algorithms in the bulk-synchronous (BSP) style on PCs distributed over the internet whose owners are willing to donate their unused computation power. PUBWCL is realized as a peer-to-peer system and features migration and restoration of BSP processes executed on it. The use of Java guarantees a high level of security and makes PUBWCL platform- independent. In order to estimate the loss of efficiency inherent in such a Java-based system, we have compared it to our C-based PUB-Library.
As the unused computation power of the participating PCs is unpredictable, we need novel strategies for load balancing that have no access to future changes of the computation power available for the application. We develop, analyze, and compare different load balancing strategies for PUBWCL. In order to handle the influence of the fluctuating available computation power, we classify the external work load.
During our evaluation of the load balancing algorithms we simulated the external work load in order to have repeatable testing conditions. With the best performing load balancing strategy we could save 39% of the execution time on average and even up to 50% in particular cases, in our test environment.
AU - Bonorden, Olaf
AU - Meyer auf der Heide, Friedhelm
AU - Gehweiler, Joachim
ID - 18999
T2 - Journal on Scalable Computing: Practice and Experience
TI - A Web Computing Environment for Parallel Algorithms in Java
ER -
TY - JOUR
AU - Kissel, J.
AU - Krauter, Stefan
ID - 8306
IS - 16
JF - Energy Policy
TI - Adaptations of Renewable Energy Policies to unstable macroeconomic situations – Case study: Wind power in Brazil
VL - 34
ER -
TY - THES
AU - Heidenreich, Jens
ID - 25530
TI - Adaptierbare Änderungsplanung der Mengen und Kapazitäten in Produktionsnetzwerken der Serienfertigung
VL - 182
ER -