06. Solving a Real-World Train Unit Assignment Problem
Valentina Cacchiani, Alberto Caprara & Paolo Toth
Conference Paper published 2007 via Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, Wadern/Saarbruecken, Germany
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...
https://doi.org/10.4230/oasics.atmos.2007.1172 Cite
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...
https://doi.org/10.4230/lipics.stacs.2010.2473 Cite
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...
https://doi.org/10.4230/oasics.cca.2009.2248 Cite
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...
https://doi.org/10.4230/lipics.fsttcs.2010.308 Cite
Towards a Parallel Virtual Machine for Functional Logic Programming
Abdulla Alqaddoumi
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...
https://doi.org/10.4230/lipics.iclp.2010.222 Cite
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
Adrian Dumitrescu & Minghui Jiang
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
We study the scheduling problem on unrelated machines in the mechanism design setting. This problem was proposed and studied in the seminal paper (Nisan and Ronen 1999), where they gave a $1.75$-approximation randomized truthful mechanism for the case of two machines. We improve this result by a $1.6737$-approximation randomized truthful mechanism. We also generalize our result to a $0.8368m$-approximation mechanism for task scheduling with $m$ machines, which improve the previous best upper bound of $0.875m(...
Towards a Common WCET Annotation Language: Essential Ingredients
Raimund Kirner, Albrecht Kadlec, Adrian Prantl, Markus Schordan & Jens Knoop
Within the last years, ambitions towards the definition of common interfaces and the development of open frameworks have increased the efficiency of research on WCET analysis. The Annotation Language Challenge for WCET analysis has been proposed in line with these ambitions in order to push the development of common interfaces also to the level of annotation languages, which are crucial for the power of WCET analysis tools. In this paper we present a list of...
https://doi.org/10.4230/oasics.wcet.2008.1657 Cite
Delay Management with Re-Routing of Passengers
Twan Dollevoet, Dennis Huisman, Marie Schmidt & Anita Schoebel
Trains often arrive delayed at stations where passengers have to change to other trains. The question of delay management is whether these trains should wait for the original train or depart on time. In traditional delay management models passengers always take their originally planned route. This means, they are in case of a missed connection always delayed with the cycle time of the timetable. In this paper, we propose a model where re-routing of passengers...
WCET Analysis of a Parallel 3D Multigrid Solver Executed on the MERASA Multi-Core
Christine Rochange, Armelle Bonenfant, Pascal Sainrat, Mike Gerdes, Julian Wolf, Theo Ungerer, Zlatko Petrov & Frantisek Mikulu
To meet performance requirements as well as constraints on cost and power consumption, future embedded systems will be designed with multi-core processors. However, the question of timing analysability is raised with these architectures. In the MERASA project, a WCET-aware multi-core processor has been designed with the appropriate system software. They both guarantee that the WCET of tasks running on different cores can be safely analyzed since their possible interactions can be bounded. Nevertheless, computing the...
https://doi.org/10.4230/oasics.wcet.2010.90 Cite
Deterministic Black-Box Identity Testing $pi$-Ordered Algebraic Branching Programs
Maurice Jansen, Youming Qiao & Jayalal Sarma M.N.
In this paper we study algebraic branching programs (ABPs) with restrictions on the order and the number of reads of variables in the program. An ABP is given by a layered directed acyclic graph with source $s$ and sink $t$, whose edges are labeled by variables taken from the set $\{x_1, x_2, \ldots, x_n\}$ or field constants. It computes the sum of weights of all paths from $s$ to $t$, where the weight of a...
New Combinatorial Complete One-Way Functions
Arist Kojevnikov & Sergey I. Nikolenko
In 2003, Leonid A. Levin presented the idea of a combinatorial complete one-way function and a sketch of the proof that Tiling represents such a function. In this paper, we present two new one-way functions based on semi-Thue string rewriting systems and a version of the Post Correspondence Problem and prove their completeness. Besides, we present an alternative proof of Levin's result. We also discuss the properties a combinatorial problem should have in order to...
Long Non-crossing Configurations in the Plane
Adrian Dumitrescu & Csaba D. Tóth
We revisit several maximization problems for geometric networks design under the non-crossing constraint, first studied by Alon, Rajagopalan and Suri (ACM Symposium on Computational Geometry, 1993). Given a set of $n$ points in the plane in general position (no three points collinear), compute a longest non-crossing configuration composed of straight line segments that is: (a) a matching (b) a Hamiltonian path (c) a spanning tree. Here we obtain new results for (b) and (c), as...
Higher-Order (Non-)Modularity
Claus Appel, Vincent Van Oostrom & Jakob Grue Simonsen
We show that, contrary to the situation in first-order term rewriting, almost none of the usual properties of rewriting are modular for higher-order rewriting, irrespective of the higher-order rewriting format. We show that for the particular format of simply typed applicative term rewriting systems modularity of confluence, normalization, and termination can be recovered by imposing suitable linearity constraints.
https://doi.org/10.4230/lipics.rta.2010.17 Cite
On Termination for Faulty Channel Machines
Patricia Bouyer, Nicolas Markey, Joël Ouaknine, Philippe Schnoebelen & James Worrell
A channel machine consists of a finite controller together with several fifo channels; the controller can read messages from the head of a channel and write messages to the tail of a channel. In this paper, we focus on channel machines with insertion errors, i.e., machines in whose channels messages can spontaneously appear. Such devices have been previously introduced in the study of Metric Temporal Logic. We consider the termination problem: are all the computations...
The Mälardalen WCET Benchmarks: Past, Present And Future
Jan Gustafsson, Adam Betts, Andreas Ermedahl & Björn Lisper
Modelling of real-time systems requires accurate and tight estimates of the Worst-Case Execution Time (WCET) of each task scheduled to run. In the past two decades, two main paradigms have emerged within the field of WCET analysis: static analysis and hybrid measurement-based analysis. These techniques have been succesfully implemented in prototype and commercial toolsets. Yet, comparison among the WCET estimates derived by such tools remains somewhat elusive as it requires a common set of benchmarks...
https://doi.org/10.4230/oasics.wcet.2010.136 Cite
The Complexity of Approximating Bounded-Degree Boolean #CSP
Martin Dyer, Leslie Ann Goldberg, Markus Jalsenius & David Richerby
The degree of a CSP instance is the maximum number of times that a variable may appear in the scope of constraints. We consider the approximate counting problem for Boolean CSPs with bounded-degree instances, for constraint languages containing the two unary constant relations $\{0\}$ and $\{1\}$. When the maximum degree is at least $25$ we obtain a complete classification of the complexity of this problem. It is exactly solvable in polynomial-time if every relation in...
From Interval Computations to Constraint-Related Set Computations: Towards Faster Estimation of Statistics and ODEs under Interval and p-Box Uncertainty (Invited Talk)
Vladik Kreinovich
Interval computations estimate the uncertainty of the result of data processing in situations in which we only know the upper bounds $\Delta$ on the measurement errors. In this case, based on the measurement result $\widetilde x$, we can only conclude that the actual (unknown) value $x$ of the desired quantity is in the interval $[\widetilde x-\Delta,\widetilde x+\Delta]$. In interval computations, at each intermediate stage of the computation, we have intervals of possible values of the...
Treewidth Reduction for Constrained Separation and Bipartization Problems
Dániel Marx, Barry O'Sullivan & Igor Razgon
We present a method for reducing the treewidth of a graph while preserving all the minimal $s-t$ separators. This technique turns out to be very useful for establishing the fixed-parameter tractability of constrained separation and bipartization problems. To demonstrate the power of this technique, we prove the fixed-parameter tractability of a number of well-known separation and bipartization problems with various additional restrictions (e.g., the vertices being removed from the graph form an independent set). These...
Fast equivalence-checking for normed context-free processes
Wojciech Czerwinski & Slawomir Lasota
Bisimulation equivalence is decidable in polynomial time over normed graphs generated by a context-free grammar. We present a new algorithm, working in time $O(n^5)$, thus improving the previously known complexity $O(n^8 * polylog(n))$. It also improves the previously known complexity $O(n^6 * polylog(n))$ of the equality problem for simple grammars.
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...
https://doi.org/10.4230/oasics.trustworthysw.2006.699 Cite
Dagstuhl