The problem of intractability and analysis of heuristics in discrete optimization. I (Q1320831)

Three discrete optimization problems of the following type are considered: Given a finite set \(X\) of points in a Euclidean space \(E\) and a vector \(c\in E\), minimize on \(X\) the linear form \((c,x)\). The author obtains high exponential lower bound for the density of the graphs of polyhedra \(\text{conv },X\) for the problems under consideration (the density of a graph is the maximum number of pairwise adjacent vertices). Effective criteria for adjacency of vertices of the associated polyhedra are found. In a number of cases, the graphs prove to be complete, i.e., their density is equal to the number of vertices.