Simple Temporal Networks (STNs) are used in many applications, as they provide a powerful and general tool for representing conjunctions of minimum and maximum distance constraints between pairs of temporal variables.During construction of an STN, it is possible that the network presents some constraint violations that need to be resolved.One way to solve such violations is to remove a minimal number of constraints, already shown to be an APX-hard problem.Another way is relaxing some constraints in different ways till violations are solved and choosing the best configuration according to one or more criteria.In this paper, assuming that it is possible to increase any constraint bound of an STN paying a constraint-specific cost, we exhibit a polynomial-time algorithm that repairs an STN eliminating all constraint violations at minimum global cost.

Optimal Design of Consistent Simple Temporal Networks

RIZZI, ROMEO;POSENATO, Roberto
2013

Abstract

Simple Temporal Networks (STNs) are used in many applications, as they provide a powerful and general tool for representing conjunctions of minimum and maximum distance constraints between pairs of temporal variables.During construction of an STN, it is possible that the network presents some constraint violations that need to be resolved.One way to solve such violations is to remove a minimal number of constraints, already shown to be an APX-hard problem.Another way is relaxing some constraints in different ways till violations are solved and choosing the best configuration according to one or more criteria.In this paper, assuming that it is possible to increase any constraint bound of an STN paying a constraint-specific cost, we exhibit a polynomial-time algorithm that repairs an STN eliminating all constraint violations at minimum global cost.
9780769551128
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11562/618753
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 0
social impact