About: Klee–Minty cube

Facets (new session)
Description
Metadata
Settings
- Rule:
- Inverse Functional Properties:
- "Same As":

About: Klee–Minty cube Goto Sponge NotDistinct Permalink

An Entity of Type : yago:Solid113860793, within Data Space : dbpedia.org associated with source document(s)
QRcode icon

http://dbpedia.org/describe/?url=http%3A%2F%2Fdbpedia.org%2Fresource%2FKlee%E2%80%93Minty_cube

The Klee–Minty cube or Klee–Minty polytope (named after Victor Klee and George J. Minty) is a unit hypercube of variable dimension whose corners have been perturbed. Klee and Minty demonstrated that George Dantzig's simplex algorithm has poor worst-case performance when initialized at one corner of their "squashed cube". On the three-dimensional version, the simplex algorithm and the criss-cross algorithm visit all 8 corners in the worst case.

Attributes	Values
rdf:type	yago:WikicatCubes yago:Abstraction100002137 yago:Attribute100024264 yago:Cube113916721 yago:Polyhedron113883885 yago:RegularPolyhedron113915999 yago:Shape100027807 yago:Solid113860793
rdfs:label	Klee–Minty cube (en)
rdfs:comment	The Klee–Minty cube or Klee–Minty polytope (named after Victor Klee and George J. Minty) is a unit hypercube of variable dimension whose corners have been perturbed. Klee and Minty demonstrated that George Dantzig's simplex algorithm has poor worst-case performance when initialized at one corner of their "squashed cube". On the three-dimensional version, the simplex algorithm and the criss-cross algorithm visit all 8 corners in the worst case. (en)
foaf:depiction
dcterms:subject	Cubes Computational complexity theory Analysis of algorithms Convex geometry Linear programming
Wikipage page ID	31302509 (xsd:integer)
Wikipage revision ID	1034990078 (xsd:integer)
Link from a Wikipage to another Wikipage	Euclidean metric Algorithm Arithmetic operation Cubes Victor Klee Degree of a polynomial Interior-point method Ellipsoidal method Worst-case complexity Criss-cross algorithm Analysis of algorithms Gaussian elimination George Dantzig Stephen Smale Unit sphere Matroid Buchberger's algorithm Time complexity Karmarkar's algorithm Linear programming Expected value Dimension (vector space) Hypercube Computational complexity theory Analysis of algorithms Convex geometry Linear programming Bland's rule George J. Minty Dimension Average-case complexity Simplex algorithm Unit cube Multivariate polynomial Linear optimization Big Oh Big oh Polynomial-time algorithm Quadratic polynomial Simplex method Günter Ziegler Cubic polynomial Exchange algorithm dbr:Central_path
Link from a Wikipage to an external page	http://www.cas.mcmaster.ca/~terlaky/files/crisscross.ps http://www.mathematik.de/ger/information/forschungsprojekte/zieglergeometrie/zieglergeometrie.html http://www.cas.mcmaster.ca/~deza/mp2008.pdf https://translate.google.com/translate%3Fsl=auto&tl=en&js=n&prev=_t&hl=en&ie=UTF-8&layout=2&eotf=1&u=http%3A%2F%2Fwww.mathematik.de%2Fger%2Finformation%2Fforschungsprojekte%2Fzieglergeometrie%2Fzieglergeometrie.html http://www.informatik.uni-trier.de/~ley/db/indices/a-tree/n/Nematollahi:Eissa.html
sameAs	Klee–Minty cube Klee–Minty cube Klee–Minty cube
dbp:wikiPageUsesTemplate	dbt:Cite_book dbt:Cite_journal dbt:Cn dbt:Efn dbt:Notelist dbt:Reflist dbt:Mathematical_programming dbt:Optimization_algorithms
thumbnail	wiki-commons:Special:FilePath/Klee-Minty-cube-for-shadow-vertex-pivot-rule.png?width=300
collapsed	yes (en)
state	collapsed (en)
has abstract	The Klee–Minty cube or Klee–Minty polytope (named after Victor Klee and George J. Minty) is a unit hypercube of variable dimension whose corners have been perturbed. Klee and Minty demonstrated that George Dantzig's simplex algorithm has poor worst-case performance when initialized at one corner of their "squashed cube". On the three-dimensional version, the simplex algorithm and the criss-cross algorithm visit all 8 corners in the worst case. In particular, many optimization algorithms for linear optimization exhibit poor performance when applied to the Klee–Minty cube. In 1973 Klee and Minty showed that Dantzig's simplex algorithm was not a polynomial-time algorithm when applied to their cube. Later, modifications of the Klee–Minty cube have shown poor behavior both for other basis-exchange pivoting algorithms and also for interior-point algorithms. (en)
gold:hypernym	Cube
prov:wasDerivedFrom	wikipedia-en:Klee–Minty_cube?oldid=1034990078&ns=0
page length (characters) of wiki page	13923 (xsd:nonNegativeInteger)
foaf:isPrimaryTopicOf	wikipedia-en:Klee–Minty_cube
is Link from a Wikipage to another Wikipage of	Cunningham's rule Victor Klee List of numerical analysis topics Criss-cross algorithm Linear programming Tamás Terlaky George J. Minty Simplex algorithm Klee-Minty cube Klee-Minty Klee-Minty polytope

Faceted Search & Find service v1.17_git139 as of Feb 29 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 08.03.3330 as of Mar 19 2024, on Linux (x86_64-generic-linux-glibc212), Single-Server Edition (61 GB total memory, 40 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software