| 1. |
|
|
| 2. |
- 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.
|
|
| 3. |
|
|
| 4. |
|
|
| 5. |
- 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.
|
|
| 6. |
|
|
| 7. |
|
|
| 8. |
- 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.
|
|
| 9. |
|
|
| 10. |
-
Communication Technologies for Vehicles : Third International Workshop, Nets4Cars/Nets4Trains 2011, Oberpfaffenhofen, Germany, March 23-24, 2011. Proceedings
- 2011
-
Proceedings (redaktörskap) (refereegranskat)abstract
- The proceedings contain 20 papers. The topics discussed include: VANET architectures and protocol stacks: a survey; behavior specification of a red-light violation warning application - an approach for specifying reactive vehicle-2-X communication applications; wireless protocol design for a cooperative pedestrian protection system; a vehicular mobility model based on real traffic counting data; driver-centric VANET simulation; simulative evaluation of the potential of Car2X-communication in terms of efficiency; performance study of an in-car switched Ethernet network without prioritization; degradation of communication range in VANETs caused by interference 2.0 - real-world experiment; real-world measurements of non-line-of-sight reception quality for 5.9GHz IEEE 802.11p at intersections; and interoperability testing suite for C2X communication components. © Springer-Verlag Berlin Heidelberg 2011
|
|
