Temporal Flexibility Revisited: Maximizing Flexibility by Computing Bipartite Matchings

Conference paper (2015)

Authors

Kiriakos Simon Mountakis Algorithmics -

T.B. Klos Algorithmics -

C. Witteveen Algorithmics -

Research Group

Algorithmics () (TU Delft)

Flexibility Simple Temporal Networks

To reference this document use:

http://resolver.tudelft.nl/uuid:2b36fe57-885b-4bce-894d-a3024f4eb205

More Info

expand_more

Published Date

2015

Language

English

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Faculty

Electrical Engineering, Mathematics and Computer Science

Department

Software Technology

Research Group

Algorithmics

Abstract

We discuss two flexibility metrics for Simple Temporal Networks (STNs): the so-called naive flexibility metric based on the difference between earliest and latest starting times of temporal variables, and a recently proposed concurrent flexibility metric. We establish an interesting connection between the computation of these flexibility metrics and properties of the minimal distance matrix DS of an STN S: the concurrent flexibility metric can be computed by finding a minimum weight matching of a weighted bipartite graph completely specified by DS, while the naive flexibility metric corresponds to computing a maximum weight matching in the same graph. From a practical point of view this correspondence offers an advantage: instead of using an O(n5) LP-based approach, reducing the problem to a matching problem we derive an O(n3) algorithm for computing the concurrent flexibility metric.