Unique sink orientation (original) (raw)
In mathematics, a unique sink orientation is an orientation of the edges of a polytope such that, in every face of the polytope (including the whole polytope as one of the faces), there is exactly one vertex for which all adjoining edges are oriented inward (i.e. towards that vertex). If a polytope is given together with a linear objective function, and edges are oriented from vertices with smaller objective function values to vertices with larger objective values, the result is a unique sink orientation. Thus, unique sink orientations can be used to model linear programs as well as certain nonlinear programs such as the smallest circle problem.
| Property | Value |
|---|---|
| dbo:abstract | In mathematics, a unique sink orientation is an orientation of the edges of a polytope such that, in every face of the polytope (including the whole polytope as one of the faces), there is exactly one vertex for which all adjoining edges are oriented inward (i.e. towards that vertex). If a polytope is given together with a linear objective function, and edges are oriented from vertices with smaller objective function values to vertices with larger objective values, the result is a unique sink orientation. Thus, unique sink orientations can be used to model linear programs as well as certain nonlinear programs such as the smallest circle problem. (en) |
| dbo:wikiPageID | 18476346 (xsd:integer) |
| dbo:wikiPageLength | 5746 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1032112008 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Face_lattice dbr:Algorithm dbr:Degree_(graph_theory) dbc:Graph_theory_objects dbr:Mathematics dbr:Acyclic_orientation dbr:Linear_complementarity_problem dbr:Linear_programming dbc:Polyhedral_combinatorics dbr:Journal_of_Combinatorial_Theory dbr:LP-type_problem dbr:Directed_acyclic_graph dbr:Polynomial_time dbr:Vertex_(graph_theory) dbr:Discrete_and_Computational_Geometry dbr:Polytope dbr:Simple_polytope dbr:Lower_set dbr:Linear_program dbr:Smallest_circle_problem |
| dbp:wikiPageUsesTemplate | dbt:Citation dbt:Harv dbt:Harvtxt dbt:Math dbt:Mvar |
| dct:subject | dbc:Graph_theory_objects dbc:Polyhedral_combinatorics |
| gold:hypernym | dbr:Orientation |
| rdf:type | yago:Object100002684 yago:PhysicalEntity100001930 yago:WikicatGraphTheoryObjects |
| rdfs:comment | In mathematics, a unique sink orientation is an orientation of the edges of a polytope such that, in every face of the polytope (including the whole polytope as one of the faces), there is exactly one vertex for which all adjoining edges are oriented inward (i.e. towards that vertex). If a polytope is given together with a linear objective function, and edges are oriented from vertices with smaller objective function values to vertices with larger objective values, the result is a unique sink orientation. Thus, unique sink orientations can be used to model linear programs as well as certain nonlinear programs such as the smallest circle problem. (en) |
| rdfs:label | Unique sink orientation (en) |
| owl:sameAs | freebase:Unique sink orientation yago-res:Unique sink orientation wikidata:Unique sink orientation https://global.dbpedia.org/id/4wkrr |
| prov:wasDerivedFrom | wikipedia-en:Unique_sink_orientation?oldid=1032112008&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Unique_sink_orientation |
| is dbo:wikiPageWikiLink of | dbr:Convex_polytope dbr:TFNP dbr:LP-type_problem dbr:Polyhedral_combinatorics dbr:Simple_polytope |
| is foaf:primaryTopic of | wikipedia-en:Unique_sink_orientation |