### 06. Solving a Real-World Train Unit Assignment Problem

Valentina Cacchiani, Alberto Caprara & Paolo Toth
We face a real-world train unit assignment problem for an operator running trains in a regional area. Given a set of timetabled train trips, each with a required number of passenger seats, and a set of train units, each with a given number of available seats, the problem calls for an assignment of the train units to trips, possibly combining more than one train unit for a given trip, that fulfills the seat requests. With...

### Evolving Multialgebras Unify All Usual Sequential Computation Models

Serge Grigorieff & Pierre Valarcher
It is well-known that Abstract State Machines (ASMs) can simulate step-by-step" any type of machines (Turing machines, RAMs, etc.). We aim to overcome two facts: 1) simulation is not identification, 2) the ASMs simulating machines of some type do not constitute a natural class among all ASMs. We modify Gurevich's notion of ASM to that of EMA (Evolving MultiAlgebra") by replacing the program (which is a syntactic object) by a semantic object: a functional which...

### CCA 2009 Front Matter - Proceedings of the Sixth International Conference on Computability and Complexity in Analysis

Andrej Bauer, Peter Hertling & Ker-I Ko
The Sixth International Conference on Computability and Complexity in Analysis, CCA 2009, took place on August 18 to 22, 2009, in Ljubljana, Slovenia. The conference is concerned with Computable Analysis, the theory of computability and complexity over real-valued data. The conference program consisted of 4 invited talks, 2 tutorials of three talks each, and 24 contributed talks. These proceedings contain the abstracts or extended abstracts of the invited talks, tutorials, and a selection of 22...

### ATMOS 2008 Abstracts Collection -- 8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems

Matteo Fischetti & Peter Widmayer
Proceedings of the 8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems, held on Septmeber 18 in Karlsruhe, Germany.

### Computing Rational Radical Sums in Uniform TC^0

Paul Hunter, Patricia Bouyer, Nicolas Markey, Joël Ouaknine & James Worrell
A fundamental problem in numerical computation and computational geometry is to determine the sign of arithmetic expressions in radicals. Here we consider the simpler problem of deciding whether $\sum_{i=1}^m C_i A_i^{X_i}$ is zero for given rational numbers $A_i$, $C_i$, $X_i$. It has been known for almost twenty years that this can be decided in polynomial time. In this paper we improve this result by showing membership in uniform TC0. This requires several significant departures from...

### Towards a Parallel Virtual Machine for Functional Logic Programming

Functional logic programming is a multi-paradigm programming that combines the best features of functional programming and logic programming. Functional programming provides mechanisms for demand-driven evaluation, higher order functions and polymorphic typing. Logic programming deals with non-determinism, partial information and constraints. Both programming paradigms fall under the umbrella of declarative programming. For the most part, the current implementations of functional logic languages belong to one of two categories: (1) Implementations that include the logic programming features...

### Deterministically Isolating a Perfect Matching in Bipartite Planar Graphs

Samir Datta, Raghav Kulkarni & Sambuddha Roy
We present a deterministic way of assigning small (log bit) weights to the edges of a bipartite planar graph so that the minimum weight perfect matching becomes unique. The isolation lemma as described in (Mulmuley et al. 1987) achieves the same for general graphs using a randomized weighting scheme, whereas we can do it deterministically when restricted to bipartite planar graphs. As a consequence, we reduce both decision and construction versions of the matching problem...

### Dispersion in Unit Disks

We present two new approximation algorithms with (improved) constant ratios for selecting $n$ points in $n$ unit disks such that the minimum pairwise distance among the points is maximized. (I) A very simple $O(n \log{n})$-time algorithm with ratio $0.5110$ for disjoint unit disks. In combination with an algorithm of Cabello~\cite{Ca07}, it yields a $O(n^2)$-time algorithm with ratio of $0.4487$ for dispersion in $n$ not necessarily disjoint unit disks. (II) A more sophisticated LP-based algorithm with...

### On Oscillation-free epsilon-random Sequences II

Jöran Mielke & Ludwig Staiger
It has been shown (see (Staiger, 2008)), that there are strongly \textsc{Martin-L\"of}-$\varepsilon$-random $\omega$-words that behave in terms of complexity like random $\omega$-words. That is, in particular, the \emph{a priori} complexity of these $\varepsilon$-random $\omega$-words is bounded from below and above by linear functions with the same slope $\varepsilon$. In this paper we will study the set of these $\omega$-words in terms of \textsc{Hausdorff} measure and dimension. Additionally we find upper bounds on \emph{a priori} complexity,...

### Determining the Winner of a Dodgson Election is Hard

Michael Fellows, Bart M. P. Jansen, Daniel Lokshtanov, Frances A. Rosamond & Saket Saurabh
Computing the Dodgson Score of a candidate in an election is a hard computational problem, which has been analyzed using classical and parameterized analysis. In this paper we resolve two open problems regarding the parameterized complexity of DODGSON SCORE. We show that DODGSON SCORE parameterized by the target score value $k$ does not have a polynomial kernel unless the polynomial hierarchy collapses to the third level; this complements a result of Fellows, Rosamond and Slinko...

### An Improved Randomized Truthful Mechanism for Scheduling Unrelated Machines

Pinyan Lu & Changyuan Yu

### Using Abstraction in Modular Verification of Synchronous Adaptive Systems

Ina Schaefer & Arnd Poetzsch-Heffter
Self-adaptive embedded systems autonomously adapt to changing environment conditions to improve their functionality and to increase their dependability by downgrading functionality in case of fail- ures. However, adaptation behaviour of embedded systems significantly complicates system design and poses new challenges for guaranteeing system correctness, in particular vital in the automotive domain. Formal verification as applied in safety-critical applications must therefore be able to address not only temporal and functional properties, but also dynamic adaptation according...

• 2010
453

• Text
453

• Dagstuhl
453