Anzeige
Erschienen in:
2016 | OriginalPaper | Buchkapitel
On Integer Recognition over Some Boolean Quadric Polytope Extension
verfasst von : Andrei Nikolaev
Erschienen in: Discrete Optimization and Operations Research
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
The problem of integer recognition is to determine whether the maximum of a linear objective function achieved at an integral vertex of a polytope. We consider integer recognition over polytope SATP and its LP relaxation \(SATP_{LP}\). These polytopes are natural extensions of the well-known Boolean quadric polytope BQP and its rooted semimetric relaxation \(BQP_{LP}\).
Integer recognition over \(SATP_{LP}\) is NP-complete, since various special instances of 3-SAT problem like NAE-3SAT and X3SAT are transformed to it. We describe polynomially solvable subproblems of integer recognition over \(SATP_{LP}\) with constrained objective functions. Based on that, we solve some cases of edge constrained bipartite graph coloring.