Access Restriction

Author El Mouelhi, A. ♦ Jegou, P. ♦ Terrioux, C.
Source IEEE Xplore Digital Library
Content type Text
Publisher Institute of Electrical and Electronics Engineers, Inc. (IEEE)
File Format PDF
Copyright Year ©2014
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Special computer methods
Subject Keyword Time complexity ♦ Polynomials ♦ Benchmark testing ♦ Artificial intelligence ♦ Algorithm design and analysis ♦ Filtering ♦ Microstructure
Abstract Tractable classes constitute an important issue in CP, at least from a theoretical viewpoint. But they are not actually used in practice. Either their treatment is too costly for time complexity or, even if there exist efficient algorithms to manage them, they do not appear in the real problems. We propose here to address this issue thanks to the notion of hidden tractable classes. Such classes are based on a known tractable class C, and a transformation t, and are defined by sets of instances P such that their transformation using t is in C, that is t (P) in C. We propose a general framework to study such notions. After, we focus our study on the tractable class BTP, and several transformations which are the filterings classically used in CP. We show then that the use of filterings allows sometimes to highlight the occurrence of BTP in the benchmarks generally considered for solver comparisons, i.e. That BTP is sometimes "hidden" in the benchmarks. Thus, this approach allows to extend the set of known tractable classes.
Description Author affiliation: LSIS, Aix-Marseille Univ., Marseille, France (El Mouelhi, A.; Jegou, P.; Terrioux, C.)
ISBN 9781479965724
ISSN 10823409
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research ♦ Reading
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2014-11-10
Publisher Place Cyprus
Rights Holder Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Size (in Bytes) 787.92 kB
Page Count 9
Starting Page 437
Ending Page 445

Source: IEEE Xplore Digital Library