This HTML5 document contains 107 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
n4http://www.cas.mcmaster.ca/~terlaky/files/
dctermshttp://purl.org/dc/terms/
n13http://www.mathematik.de/ger/information/forschungsprojekte/zieglergeometrie/
dbohttp://dbpedia.org/ontology/
n19http://dbpedia.org/resource/File:
foafhttp://xmlns.com/foaf/0.1/
n15https://global.dbpedia.org/id/
n23https://translate.google.com/
yagohttp://dbpedia.org/class/yago/
n24http://www.cas.mcmaster.ca/~deza/
dbthttp://dbpedia.org/resource/Template:
rdfshttp://www.w3.org/2000/01/rdf-schema#
freebasehttp://rdf.freebase.com/ns/
n17http://www.informatik.uni-trier.de/~ley/db/indices/a-tree/n/Nematollahi:
n16http://commons.wikimedia.org/wiki/Special:FilePath/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
owlhttp://www.w3.org/2002/07/owl#
wikipedia-enhttp://en.wikipedia.org/wiki/
dbphttp://dbpedia.org/property/
dbchttp://dbpedia.org/resource/Category:
provhttp://www.w3.org/ns/prov#
xsdhhttp://www.w3.org/2001/XMLSchema#
wikidatahttp://www.wikidata.org/entity/
goldhttp://purl.org/linguistics/gold/
dbrhttp://dbpedia.org/resource/

Statements

Subject Item
dbr:Cunningham's_rule
dbo:wikiPageWikiLink
dbr:Klee–Minty_cube
Subject Item
dbr:Victor_Klee
dbo:wikiPageWikiLink
dbr:Klee–Minty_cube
dbo:knownFor
dbr:Klee–Minty_cube
Subject Item
dbr:List_of_numerical_analysis_topics
dbo:wikiPageWikiLink
dbr:Klee–Minty_cube
Subject Item
dbr:Criss-cross_algorithm
dbo:wikiPageWikiLink
dbr:Klee–Minty_cube
Subject Item
dbr:Linear_programming
dbo:wikiPageWikiLink
dbr:Klee–Minty_cube
Subject Item
dbr:Tamás_Terlaky
dbo:wikiPageWikiLink
dbr:Klee–Minty_cube
Subject Item
dbr:George_J._Minty
dbo:wikiPageWikiLink
dbr:Klee–Minty_cube
Subject Item
dbr:Klee–Minty_cube
rdf:type
yago:Polyhedron113883885 yago:Abstraction100002137 yago:Shape100027807 yago:RegularPolyhedron113915999 yago:WikicatCubes yago:Attribute100024264 yago:Cube113916721 yago:Solid113860793
rdfs:label
Klee–Minty cube
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.
foaf:depiction
n16:Klee-Minty-cube-for-shadow-vertex-pivot-rule.png n16:Simplex_description.png
dcterms:subject
dbc:Computational_complexity_theory dbc:Analysis_of_algorithms dbc:Cubes dbc:Linear_programming dbc:Convex_geometry
dbo:wikiPageID
31302509
dbo:wikiPageRevisionID
1034990078
dbo:wikiPageWikiLink
dbr:Simplex_method dbr:Hypercube dbr:George_Dantzig dbr:Worst-case_complexity dbr:Arithmetic_operation dbr:Unit_cube dbc:Computational_complexity_theory dbr:Linear_programming dbr:Interior-point_method dbr:Victor_Klee dbr:Günter_Ziegler dbr:Karmarkar's_algorithm dbr:Quadratic_polynomial dbr:Central_path dbr:Average-case_complexity dbr:Multivariate_polynomial dbr:Gaussian_elimination dbc:Analysis_of_algorithms dbr:Algorithm dbr:Matroid dbr:Expected_value dbr:George_J._Minty n19:Simplex_description.png dbr:Cubic_polynomial dbr:Exchange_algorithm dbc:Linear_programming dbr:Polynomial-time_algorithm dbc:Cubes dbr:Degree_of_a_polynomial dbr:Big_oh dbr:Time_complexity dbc:Convex_geometry dbr:Unit_sphere dbr:Buchberger's_algorithm dbr:Linear_optimization dbr:Ellipsoidal_method dbr:Dimension_(vector_space) dbr:Dimension n19:Klee-Minty-cube-for-shadow-vertex-pivot-rule.png dbr:Simplex_algorithm dbr:Euclidean_metric dbr:Bland's_rule dbr:Big_Oh dbr:Stephen_Smale dbr:Criss-cross_algorithm dbr:Analysis_of_algorithms
dbo:wikiPageExternalLink
n4:crisscross.ps n13:zieglergeometrie.html n17:Eissa.html n23: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 n24:mp2008.pdf
owl:sameAs
n15:4pTgf wikidata:Q6420102 freebase:m.0gj9y1p
dbp:wikiPageUsesTemplate
dbt:Mathematical_programming dbt:Cite_book dbt:Optimization_algorithms dbt:Cite_journal dbt:Reflist dbt:Cn dbt:Efn dbt:Notelist
dbo:thumbnail
n16:Klee-Minty-cube-for-shadow-vertex-pivot-rule.png?width=300
dbp:collapsed
yes
dbp:state
collapsed
dbo: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.
gold:hypernym
dbr:Cube
prov:wasDerivedFrom
wikipedia-en:Klee–Minty_cube?oldid=1034990078&ns=0
dbo:wikiPageLength
13923
foaf:isPrimaryTopicOf
wikipedia-en:Klee–Minty_cube
Subject Item
dbr:Simplex_algorithm
dbo:wikiPageWikiLink
dbr:Klee–Minty_cube
Subject Item
dbr:Klee-Minty_cube
dbo:wikiPageWikiLink
dbr:Klee–Minty_cube
dbo:wikiPageRedirects
dbr:Klee–Minty_cube
Subject Item
dbr:Klee-Minty
dbo:wikiPageWikiLink
dbr:Klee–Minty_cube
dbo:wikiPageRedirects
dbr:Klee–Minty_cube
Subject Item
dbr:Klee-Minty_polytope
dbo:wikiPageWikiLink
dbr:Klee–Minty_cube
dbo:wikiPageRedirects
dbr:Klee–Minty_cube
Subject Item
dbr:Klee_Minty_cube
dbo:wikiPageWikiLink
dbr:Klee–Minty_cube
dbo:wikiPageRedirects
dbr:Klee–Minty_cube
Subject Item
wikipedia-en:Klee–Minty_cube
foaf:primaryTopic
dbr:Klee–Minty_cube