On K^

combinatorial-facial structure convex hull of extreme points Hamiltonian chains maximum capacity cuts NP-complete system of linear constraints unbounded convex polyhedral subset

Mathematics Subject Classification ID

Polytopes and polyhedra (52Bxx) Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27)

Review text

Let \({\mathbb{K}}\) be an unbounded convex polyhedral subset of \({\mathbb{R}}^ n\) represented by a system of linear constraints, and let \({\mathbb{K}}^{\Delta}\) be the convex hull of the set of extreme points of \({\mathbb{K}}\). We show that the combinatorial-facial structure of \({\mathbb{K}}\) does not uniquely determine the combinatorial-facial structure of \({\mathbb{K}}^{\Delta}\). We prove that the problem of checking whether two given extreme points of \({\mathbb{K}}\) are nonadjacent on \({\mathbb{K}}^{\Delta}\), is NP-complete in the strong sense. We show that the problem of deriving a linear constraint representation of \({\mathbb{K}}^{\Delta}\), leads to the question of checking whether the dimension of \({\mathbb{K}}^{\Delta}\) is the same as that of \({\mathbb{K}}\), and we prove that resolving this question is hard because it needs the solution of some NP-complete problems. Finally we provide a formula for the dimension of \({\mathbb{K}}^{\Delta}\), under a nondegeneracy assumption.

Recommendations

Cites work

Cited in

(3)

This page was built for publication: On \({\mathbb{K}}^{\Delta}\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1821691)