A spectral approach to polyhedral dimension

descriptionPublicationkeyboard_double_arrow_right Article 01 May 1990 English Publisher:Springer Science and Business Media LLCJournal:Mathematical Programming, volume 47, pages 441-459 (issn: 0025-5610, eissn: 1436-4646,

Copyright policy )

Authors: Jon Lee 0001;

doi: 10.1007/bf01580874

A spectral approach to polyhedral dimension

- Summary
- Subjects
- Metrics

Abstract

The author defines a new dimension function for polytopes using the convex hull of the edge or arc incidence vectors of Hamiltonian tours and other objects in graphs. A matrix with rows equal to the extreme points of the polytope and supplemented with a column of units is constructed. The matrix is reduced to diagonal form by orthogonal transformations. The number of nonzero diagonal elements defines the dimension of the polytope. Values of such diagonal elements are obtained for some graphs and hypergraphs.

Related Organizations

Yale University
United States

Keywords

dimension function, Combinatorial optimization, polyhedral dimension, Hamiltonian tours, Special polytopes (linear programming, centrally symmetric, etc.), Integer programming, Programming involving graphs or networks, spectrum

Impact byBIP!

	selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	3
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Average
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Top 10%
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Average