TY - CONF
AB - We consider a scheduling problem where machines need to be rented from the cloud in order to process jobs. There are two types of machines available which can be rented for machine-type dependent prices and for arbitrary durations. However, a machine-type dependent setup time is required before a machine is available for processing. Jobs arrive online over time, have machine-type dependent sizes and have individual deadlines. The objective is to rent machines and schedule jobs so as to meet all deadlines while minimizing the rental cost. Since we observe the slack of jobs to have a fundamental influence on the competitiveness, we study the model when instances are parameterized by their (minimum) slack. An instance is called to have a slack of $\beta$ if, for all jobs, the difference between the job's release time and the latest point in time at which it needs to be started is at least $\beta$. While for $\beta series = {LNCS}
AU - Mäcker, Alexander
AU - Malatyali, Manuel
AU - Meyer auf der Heide, Friedhelm
AU - Riechers, Sören
ID - 207
T2 - Proceedings of the 10th Annual International Conference on Combinatorial Optimization and Applications (COCOA)
TI - Cost-efficient Scheduling on Machines from the Cloud
ER -
TY - CONF
AB - We present PAndA2, an extendable, static analysis tool for Android apps which examines permission related security threats like overprivilege, existence of permission redelegation and permission flows. PAndA2 comes along with a textual and graphical visualization of the analysis result and even supports the comparison of analysis results for different android app versions.
AU - Jakobs, Marie-Christine
AU - Töws, Manuel
AU - Pauck, Felix
ED - Ishikawa F, Romanovsky A, Troubitsyna E
ID - 170
T2 - Workshop on Formal and Model-Driven Techniques for Developing Trustworthy Systems
TI - PAndA 2 : Analyzing Permission Use and Interplay in Android Apps (Tool Paper)
ER -
TY - GEN
AU - Kesmen, Belma
ID - 182
TI - Marktmissbrauch in der Internetökonomie - Eine wettbewerbspolitische Analyse
ER -
TY - CHAP
AU - W. Richa, Andrea
AU - Scheideler, Christian
ID - 1845
T2 - Encyclopedia of Algorithms
TI - Jamming-Resistant MAC Protocols for Wireless Networks
ER -
TY - GEN
ED - Meyer auf der Heide, Friedhelm
ID - 187
IS - 1
T2 - Transactions on Parallel Computing (TOPC)
TI - Introduction to the Special Issue on SPAA 2014
ER -
TY - JOUR
AB - Today, service compositions often need to be assembled or changed on-the-fly, which leaves only little time for quality assurance. Moreover, quality assurance is complicated by service providers only giving information on their services in terms of domain specific concepts with only limited semantic meaning.In this paper, we propose a method for constructing service compositions based on pre-verified templates. Templates, given as workflow descriptions, are typed over a (domain-independent) template ontology defining concepts and predicates. Their meaning is defined by an abstract semantics, leaving the specific meaning of ontology concepts open, however, only up to given ontology rules. Templates are proven correct using a Hoare-style proof calculus, extended by a specific rule for service calls. Construction of service compositions amounts to instantiation of templates with domain-specific services. Correctness of an instantiation can then simply be checked by verifying that the domain ontology (a) adheres to the rules of the template ontology, and (b) fulfills the constraints of the employed template.
AU - Walther, Sven
AU - Wehrheim, Heike
ID - 175
JF - Science of Computer Programming
TI - On-The-Fly Construction of Provably Correct Service Compositions - Templates and Proofs
ER -
TY - JOUR
AB - We construct two-player two-strategy game-theoretic models of by-product mutualism, where our focus lies on the way in which the probability of cooperation among players is affected by the degree of adversity facing the players. In our first model, cooperation consists of the production of a public good, and adversity is linked to the degree of complementarity of the players׳ efforts in producing the public good. In our second model, cooperation consists of the defense of a public, and/or a private good with by-product benefits, and adversity is measured by the number of random attacks (e.g., by a predator) facing the players. In both of these models, our analysis confirms the existence of the so-called boomerang effect, which states that in a harsh environment, the individual player has few incentives to unilaterally defect in a situation of joint cooperation. Focusing on such an effect in isolation leads to the "common-enemy" hypothesis that a larger degree of adversity increases the probability of cooperation. Yet, we also find that a sucker effect may simultaneously exist, which says that in a harsh environment, the individual player has few incentives to unilaterally cooperate in a situation of joint defection. Looked at in isolation, the sucker effect leads to the competing hypothesis that a larger degree of adversity decreases the probability of cooperation. Our analysis predicts circumstances in which the "common enemy" hypothesis prevails, and circumstances in which the competing hypothesis prevails.
AU - De Jaegher, Kris
AU - Hoyer, Britta
ID - 1922
JF - Journal of Theoretical Biology
SN - 0022-5193
TI - By-product mutualism and the ambiguous effects of harsher environments – A game-theoretic model
VL - 393
ER -
TY - GEN
AU - Sassenberg, Tristan
ID - 194
TI - Gefälschte Online Bewertungen - Literaturüberblick
ER -
TY - GEN
AU - Bemmann, Kai Sören
ID - 214
TI - Commitment Schemes - Definitions, Variants, and Security
ER -
TY - CONF
AB - One of the most popular fuzzy clustering techniques is the fuzzy K-means algorithm (also known as fuzzy-c-means or FCM algorithm). In contrast to the K-means and K-median problem, the underlying fuzzy K-means problem has not been studied from a theoretical point of view. In particular, there are no algorithms with approximation guarantees similar to the famous K-means++ algorithm known for the fuzzy K-means problem. This work initiates the study of the fuzzy K-means problem from an algorithmic and complexity theoretic perspective. We show that optimal solutions for the fuzzy K-means problem cannot, in general, be expressed by radicals over the input points. Surprisingly, this already holds for simple inputs in one-dimensional space. Hence, one cannot expect to compute optimal solutions exactly. We give the first (1+eps)-approximation algorithms for the fuzzy K-means problem. First, we present a deterministic approximation algorithm whose runtime is polynomial in N and linear in the dimension D of the input set, given that K is constant, i.e. a polynomial time approximation scheme (PTAS) for fixed K. We achieve this result by showing that for each soft clustering there exists a hard clustering with similar properties. Second, by using techniques known from coreset constructions for the K-means problem, we develop a deterministic approximation algorithm that runs in time almost linear in N but exponential in the dimension D. We complement these results with a randomized algorithm which imposes some natural restrictions on the sought solution and whose runtime is comparable to some of the most efficient approximation algorithms for K-means, i.e. linear in the number of points and the dimension, but exponential in the number of clusters.
AU - Blömer, Johannes
AU - Brauer, Sascha
AU - Bujna, Kathrin
ID - 2367
KW - unsolvability by radicals
KW - clustering
KW - fuzzy k-means
KW - probabilistic method
KW - approximation algorithms
KW - randomized algorithms
SN - 9781509054732
T2 - 2016 IEEE 16th International Conference on Data Mining (ICDM)
TI - A Theoretical Analysis of the Fuzzy K-Means Problem
ER -