资源论文Linear Satisfiability Preserving Assignments (Extended Abstract) ? Kei Kimura1 and Kazuhisa Makino2

Linear Satisfiability Preserving Assignments (Extended Abstract) ? Kei Kimura1 and Kazuhisa Makino2

2019-11-06 | |  58 |   41 |   0
Abstract In this paper, we study several classes of satisfiability preserving assignments to the constraint satisfaction problem. In particular, we consider fixable, autark and satisfying assignments. Since it is in general NP-hard to find a nontrivial (i.e., nonempty) satisfiability preserving assignment, we introduce linear satisfiability preserving assignments, which are defined by polyhedral cones in an associated vector space. The vector space is obtained by the identification, introduced by Kullmann, of assignments with real vectors. We consider arbitrary polyhedral cones, where only restricted classes of cones for autark assignments are considered in the literature. We reveal that cones in certain classes are maximal as a convex subset of the set of the associated vectors, which can be regarded as extensions of Kullmann’s results for autark assignments of CNFs. As algorithmic results, we present a pseudo-polynomial time algorithm that computes a linear fixable assignment for a given integer linear system, which implies the well known pseudo-polynomial solvability for integer linear systems such as two-variableper-inequality, Horn and q-Horn systems.

上一篇:Constrained Coalition Formation on Valuation Structures: Formal Framework,

下一篇:Impossibility in Belief Merging (Extended Abstract)? Amílcar Mata Díaz and Ramón Pino Pérez

用户评价
全部评价

热门资源

  • Learning to Predi...

    Much of model-based reinforcement learning invo...

  • Stratified Strate...

    In this paper we introduce Stratified Strategy ...

  • The Variational S...

    Unlike traditional images which do not offer in...

  • A Mathematical Mo...

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

  • Rating-Boosted La...

    The performance of a recommendation system reli...