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

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

Namespace Prefixes

PrefixIRI
n17http://www.cas.mcmaster.ca/~terlaky/files/
dctermshttp://purl.org/dc/terms/
yago-reshttp://yago-knowledge.org/resource/
dbohttp://dbpedia.org/ontology/
foafhttp://xmlns.com/foaf/0.1/
n13http://dbpedia.org/resource/File:
n8https://global.dbpedia.org/id/
yagohttp://dbpedia.org/class/yago/
dbthttp://dbpedia.org/resource/Template:
n25http://www.cs.elte.hu/opres/orr/download/ORR03_1.pdf%7Cformat=pdf%3C!--%7Ceprint=http:/www.tandfonline.com/doi/pdf/10.1080/
rdfshttp://www.w3.org/2000/01/rdf-schema#
n23https://web.archive.org/web/20110728105643/http:/www.ifor.math.ethz.ch/~fukuda/publ/
freebasehttp://rdf.freebase.com/ns/
n21http://bn.dbpedia.org/resource/
n15http://commons.wikimedia.org/wiki/Special:FilePath/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
n22https://web.archive.org/web/20110728105602/http:/www.ifor.math.ethz.ch/~fukuda/
n20http://coral.ie.lehigh.edu/~terlaky/
owlhttp://www.w3.org/2002/07/owl#
n6http://core.ac.uk/download/pdf/6714737.pdf%7Cdoi=10.1016/
wikipedia-enhttp://en.wikipedia.org/wiki/
n19http://www.sciencedirect.com/science/article/B6VCT-3W3DFHB-M/2/
dbchttp://dbpedia.org/resource/Category:
dbphttp://dbpedia.org/property/
provhttp://www.w3.org/ns/prov#
xsdhhttp://www.w3.org/2001/XMLSchema#
wikidatahttp://www.wikidata.org/entity/
dbrhttp://dbpedia.org/resource/

Statements

Subject Item
dbr:Criss-cross_algorithm
rdf:type
yago:Algorithm105847438 yago:PsychologicalFeature100023100 yago:Activity100407535 yago:YagoPermanentlyLocatedEntity yago:WikicatExchangeAlgorithms owl:Thing yago:WikicatCombinatorialAlgorithms yago:WikicatGeometricAlgorithms yago:Rule105846932 yago:Abstraction100002137 yago:Event100029378 yago:WikicatOptimizationAlgorithmsAndMethods yago:Procedure101023820 yago:Act100030358
rdfs:label
Criss-cross algorithm
rdfs:comment
In mathematical optimization, the criss-cross algorithm is any of a family of algorithms for linear programming. Variants of the criss-cross algorithm also solve more general problems with linear inequality constraints and nonlinear objective functions; there are criss-cross algorithms for linear-fractional programming problems, quadratic-programming problems, and linear complementarity problems.
rdfs:seeAlso
dbr:Linear_programming
foaf:depiction
n15:Max-flow_min-cut_example.svg n15:Unitcube.svg n15:Simplex_description.png n15:Ellipsoid_2.png
dcterms:subject
dbc:Combinatorial_algorithms dbc:Exchange_algorithms dbc:Oriented_matroids dbc:Geometric_algorithms dbc:Optimization_algorithms_and_methods dbc:Combinatorial_optimization dbc:Linear_programming
dbo:wikiPageID
31255067
dbo:wikiPageRevisionID
1094666421
dbo:wikiPageWikiLink
dbr:Worst_case_complexity dbr:Sufficient_matrix dbc:Linear_programming dbr:Linear_inequality dbr:Sign_function dbc:Combinatorial_algorithms dbr:Cubic_polynomial dbr:Quadratic_programming dbr:P-matrix dbr:George_J._Minty dbr:Vertex_enumeration_problem dbr:Principal_minor dbr:Linear_system dbr:Tamas_Terlaky dbr:Victor_Klee dbr:Facet dbr:Karmarkar dbr:Simplex_algorithm n13:Unitcube.svg dbr:Combinatorics dbr:Linear_algebra dbr:Buchberger's_algorithm dbr:George_Dantzig dbr:Discrete_and_Computational_Geometry dbr:Linear_complementarity_problem dbr:Time_complexity dbr:Interior-point_method dbr:David_Avis dbr:Bland's_rule dbr:Oriented_matroid dbr:Big_Oh_notation dbc:Oriented_matroids dbr:Average_case_complexity dbc:Exchange_algorithms dbr:Linear_programming dbr:Dimension_(vector_space) dbr:Average-case_complexity dbr:Karmarkar's_algorithm dbc:Geometric_algorithms dbr:Gaussian_elimination dbr:Space_complexity dbr:Klee–Minty_cube n13:Max-flow_min-cut_example.svg dbr:Michael_J._Todd_(mathematician) dbr:Optimization_(mathematics) dbr:Worst-case_complexity dbr:Ellipsoidal_algorithm dbr:Algorithm dbr:Linear-fractional_programming dbr:Polyhedron dbr:Arithmetic_operation dbr:Real_number dbr:Multivariate_polynomial dbr:Khachiyan dbr:Big_oh dbc:Optimization_algorithms_and_methods dbr:Degree_of_a_polynomial dbr:Farkas_lemma n13:Ellipsoid_2.png dbr:Unit_cube dbr:Convex_hull dbc:Combinatorial_optimization dbr:Nonlinear_programming n13:Simplex_description.png dbr:Positive-definite_matrix dbr:Jack_Edmonds dbr:Komei_Fukuda
dbo:wikiPageExternalLink
n6:0024-3795(93)90124-7%7Cmr=1221693%7Cdoi-access=free n17:dut-twi-96-103.ps.gz n17:crisscross.ps n19:4b0e2fcfc2a71e8c14c61640b32e805a n20:publications n22: n23:publ.html n20: n25:10556780500095009--%3E
owl:sameAs
n8:ftTy yago-res:Criss-cross_algorithm wikidata:Q17006040 n21:ক্রিস-ক্রস_এ্যালগোরিদম freebase:m.0gj964k
dbp:wikiPageUsesTemplate
dbt:Cite_journal dbt:Use_dmy_dates dbt:Expand_section dbt:! dbt:About dbt:See_also dbt:Short_description dbt:Mathematical_programming dbt:Optimization_algorithms
dbo:thumbnail
n15:Unitcube.svg?width=300
dbo:abstract
In mathematical optimization, the criss-cross algorithm is any of a family of algorithms for linear programming. Variants of the criss-cross algorithm also solve more general problems with linear inequality constraints and nonlinear objective functions; there are criss-cross algorithms for linear-fractional programming problems, quadratic-programming problems, and linear complementarity problems. Like the simplex algorithm of George B. Dantzig, the criss-cross algorithm is not a polynomial-time algorithm for linear programming. Both algorithms visit all 2D corners of a (perturbed) cube in dimension D, the Klee–Minty cube (after Victor Klee and George J. Minty), in the worst case. However, when it is started at a random corner, the criss-cross algorithm on average visits only D additional corners. Thus, for the three-dimensional cube, the algorithm visits all 8 corners in the worst case and exactly 3 additional corners on average.
prov:wasDerivedFrom
wikipedia-en:Criss-cross_algorithm?oldid=1094666421&ns=0
dbo:wikiPageLength
24298
foaf:isPrimaryTopicOf
wikipedia-en:Criss-cross_algorithm