The problem of intractability and analysis of heuristics in discrete optimization. I
type: Item
instance of: scholarly article
title: The problem of intractability and analysis of heuristics in discrete optimization. I
zbMATH Open document ID: 0805.90089
author: V. A. Bondarenko
published in: Automation and Remote Control
publication date: 1994-05-24T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 90C99
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 90C60
Mathematics Subject Classification ID: 49J52
zbMATH DE Number: 561114
zbMATH Keywords: linear form
zbMATH Keywords: discrete optimization problems
MaRDI profile type: Publication
Recommended article: Intractability and analysis of heuristics for discrete optimization. II
Recommended article: Problems of discrete optimization: challenges and main approaches to solve them
Recommended article: Multiheuristic approach to discrete optimization problems
Recommended article: Analysis of discrete optimization algorithms using incomplete information
Recommended article: Q4880741
Recommended article: Q3823408
Recommended article: Q3975934
Recommended article: On a primal-proximal heuristic in discrete optimization
Recommended article: Analysis of heuristic solutions to the best choice problem.
description: scientific article; zbMATH DE number 561114