资源论文On Broken Triangles

On Broken Triangles

2019-11-25 | |  60 |   36 |   0
Abstract A binary CSP instance satisfying the brokentriangle property (BTP) can be solved in polynomial time. Unfortunately, in practice, few instances satisfy the BTP. We show that a local version of the BTP allows the merging of domain values in binary CSPs, thus providing a novel polynomial-time reduction operation. Experimental trials on benchmark instances demonstrate a significant decrease in instance size for certain classes of problems. We show that BTP-merging can be generalised to instances with constraints of arbitrary arity. A directional version of the general-arity BTP then allows us to extend the BTP tractable class previously defined only for binary CSP.

上一篇:Detecting Student Emotions in Computer-Enabled Classrooms

下一篇:Sequencing Operator Counts

用户评价
全部评价

热门资源

  • The Variational S...

    Unlike traditional images which do not offer in...

  • Learning to Predi...

    Much of model-based reinforcement learning invo...

  • Stratified Strate...

    In this paper we introduce Stratified Strategy ...

  • A Mathematical Mo...

    Direct democracy, where each voter casts one vo...

  • Rating-Boosted La...

    The performance of a recommendation system reli...