| 1. |
- Cheraghchi, M., et al.
(författare)
-
Approximating Linear Threshold Predicates
- 2010
-
Ingår i: Lecture Notes in Computer Science. 13th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2010 and 14th International Workshop on Randomization and Computation, RANDOM 2010, Barcelona, 1-3 September 2010. - Berlin, Heidelberg : Springer Berlin Heidelberg. - 0302-9743 .- 1611-3349. - 9783642153686 ; 6302, s. 110-123
-
Konferensbidrag (refereegranskat)abstract
- We study constraint satisfaction problems on the domain {-1,1}, where the given constraints are homogeneous linear threshold predicates. That is, predicates of the form sgn(w1 x1+⋯+wn x n ) for some positive integer weights w 1, ..., w n . Despite their simplicity, current techniques fall short of providing a classification of these predicates in terms of approximability. In fact, it is not easy to guess whether there exists a homogeneous linear threshold predicate that is approximation resistant or not. The focus of this paper is to identify and study the approximation curve of a class of threshold predicates that allow for non-trivial approximation. Arguably the simplest such predicate is the majority predicate sgn(x 1+⋯+xn ), for which we obtain an almost complete understanding of the asymptotic approximation curve, assuming the Unique Games Conjecture. Our techniques extend to a more general class of "majority-like" predicates and we obtain parallel results for them. In order to classify these predicates, we introduce the notion of Chow-robustness that might be of independent interest.
|
|
| 2. |
- Aguilar, Xavier, et al.
(författare)
-
MPI Trace Compression Using Event Flow Graphs
- 2014
-
Konferensbidrag (refereegranskat)abstract
- Understanding how parallel applications behave is crucial for using high-performance computing (HPC) resources efficiently. However, the task of performance analysis is becoming increasingly difficult due to the growing complexity of scientific codes and the size of machines. Even though many tools have been developed over the past years to help in this task, current approaches either only offer an overview of the application discarding temporal information, or they generate huge trace files that are often difficult to handle.In this paper we propose the use of event flow graphs for monitoring MPI applications, a new and different approach that balances the low overhead of profiling tools with the abundance of information available from tracers. Event flow graphs are captured with very low overhead, require orders of magnitude less storage than standard trace files, and can still recover the full sequence of events in the application. We test this new approach with the NERSC-8/Trinity Benchmark suite and achieve compression ratios up to 119x.
|
|
| 3. |
- Böckenhauer, Hans-Joachim, et al.
(författare)
-
The Steiner tree reoptimization problem with sharpenedtriangle inequality
- 2010
-
Konferensbidrag (refereegranskat)abstract
- In this paper, we deal with several reoptimization variants of the Steiner tree problem in graphs obeying a sharpened β-triangle inequality. A reoptimization algorithm exploits theknowledge of an optimal solution to a problem instance for finding good solutions for a locally modified instance. We show that, in graphs satisfying a sharpened triangleinequality (and even in graphs where edge-costs are restricted to the values 1 and 1∈+∈γ for an arbitrary small γ>∈0), Steiner tree reoptimization still is NP-hard for several different types of local modifications, and even APX-hard for some of them. As for theupper bounds, for some local modifications, we design linear-time (1/2∈+∈β)-approximation algorithms, and even polynomial-time approximation schemes, whereas for metric graphs (β=∈1), none of these reoptimization variants is known to permit a PTAS. As a building block for some of these algorithms, we employ a 2β-approximation algorithm for the classical Steiner tree problem on such instances, which might be of independent interest since it improves over the previously best known ratio for any β∈<∈1/2∈+∈ln (3)/4∈≈∈0.775.
|
|
| 4. |
- Chen, DeJiu, et al.
(författare)
-
Modelling Support for Design of Safety-Critical Automotive Embedded Systems
- 2008
-
Ingår i: Proceedings of the 27th International Conference on Computer Safety, Reliability and Security, 2008.. - Berlin, Heidelberg : Springer Berlin Heidelberg.
-
Konferensbidrag (refereegranskat)abstract
- This paper describes and demonstrates an approach that promises to bridge the gap between model-based systems engineering and the safety process of automotive embedded systems. The basis for this is the integration of safety analysis techniques, a method for developing and managing Safety Cases, and a systematic approach to model-based engineering - the EAST-ADL2 architecture description language. Three areas are highlighted: (I) System model development on different levels of abstraction. This enables fulfilling many requirements on software development as specified by ISO-CD-26262 (2) Safety Case development in close connection to the system model (3) Analysis of mal-functional behaviour that may cause hazards, by modelling of errors and error propagation in a (complex and hierarchical) system model.
|
|
| 5. |
- Izosimov, Viacheslav, et al.
(författare)
-
Requirement Decomposition and Testability in Development of Safety-Critical Automotive Components
- 2012
-
Konferensbidrag (refereegranskat)abstract
- 2ISO26262 is a recently approved standard for functional safety in road vehicles. It provides guidelines on minimization of unreasonable safety risks during development of embedded systems in road vehicles. However, the development process specified in ISO26262 involves a number of steps that will require changing traditional and well established development processes. In a transition phase, however, due to lack of tool support, the steps may be performed manually, increasing the risk for delays and increased cost. This paper describes a case study in which we have successfully worked with traceability and testability of functional safety requirements, as well as safety requirements assigned to a testing tool that automates integration and verification steps, leading to standard-compliant tool qualification. Our tool qualification method employs fault injection as a validation method to increase confidence in the tool. Our case study will help to avoid many of the new pitfalls that can arise when attempting to realize standard-compliant development.
|
|
| 6. |
- Lampis, Michael, et al.
(författare)
-
Scrabble is PSPACE-Complete
- 2012
-
Konferensbidrag (refereegranskat)abstract
- In this paper we study the computational complexity of the game of Scrabble.We prove the PSPACE-completeness of a derandomized model of the game, answeringan open question of Erik Demaine and Robert Hearn.
|
|
| 7. |
|
|
| 8. |
-
Principles and Practice of Constraint Programing-CP 2013 : 19th International Conference, CP 2013, Uppsala, Sweden, September 16-20, 2013, Proceedings
- 2013
-
Samlingsverk (redaktörskap) (refereegranskat)abstract
- This book constitutes the refereed conference proceedings of the 19th International Conference on Principles and Practice of Constraint Programming (CP 2013), held in Uppsala, Sweden, in September 2013. The 59 revised papers presented together with 5 invited talks were carefully selected from 170 submissions. The scope of the conference is on all aspects of computing with constraints, including: theory, algorithms, environments, languages, models and systems, applications such as decision making, resource allocation, and agreement technologies.
|
|
| 9. |
- Schaefer, Ina, et al.
(författare)
-
Compositional Algorithmic Verification of Software Product Lines
- 2010
-
Konferensbidrag (refereegranskat)abstract
- Software product line engineering allows large software systems to be developed and adapted for varying customer needs. The products of a software product line can be described by means of a {\em hierarchical variability model} specifying the commonalities and variabilities between the artifacts of the individual products. The number of products generated by a hierarchical model is exponential in its size, which poses a serious challenge to software product line analysis and verification. For an analysis technique to scale, the effort has to be linear in the size of the model rather than linear in the number of products it generates. Hence, efficient product line verification is only possible if {\em compositional} verification techniques are applied that allow the analysis of products to be {\em relativized} on the properties of their variation points. In this paper, we propose simple hierarchical variability models (SHVM) with explicit variation points as a novel way to describe a set of products consisting of sets of methods. SHVMs provide a trade--off between expressiveness and a clean and simple model suitable for compositional verification. We generalize a previously developed compositional technique and tool set for the automatic verification of control--flow based temporal safety properties to product lines defined by SHVMs, and prove soundness of the generalization. The desired property relativization is achieved by introducing variation point specifications. We evaluate the proposed technique on a number of test cases.
|
|
| 10. |
|
|
