nach oben

Annals of Data Science

Erschienen in:

01.03.2014

Discussions on Hirsch Conjecture and The Existence of Strongly Polynomial: Time Simplex Variants

verfasst von: Pei-Zhuang Wang

Erschienen in: Annals of Data Science | Ausgabe 1/2014

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Based on the theory of cone-cutting, a preliminary analysis for Hirsch conjecture is made in the paper. The author indirectly proves a related assembling conjecture under condition ‘Fully cuts’ and suggests a relaxed conjecture to deny the existence of super polynomial diameters on LP polytopes. An algorithm named Gradient Falling searching the dual optimal point y* in dual space \(Y\) from a given feasible point is presented, which traces a shortest path within the dual feasible region \(D\), the author guesses, it may be an example for the existence of strongly polynomial-times LP algorithms.

Vorheriger Artikel Proposal of New Objective Measures for Mining Association Rules: Cannibalization and Unexpectedness

Nächster Artikel Heterogeneous Embedding via Aggregating Multiple Sources

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Dantzig GB (2002) Linear programming. Oper Res 50(1):42–47CrossRef

Shi Y (2001) Multiple criteria and multiple constraint levels linear programming. World Scientific Publishing, River EdgeCrossRef

Smale S (1998) Mathematical problems for the next century. Math Intell 20(2):7–15CrossRef

Santos F, A counterexample to the Hirsch conjecture. In: Presented at the conference 100 Years in Seattle: the mathematics of Klee and Gr\(\ddot{u}\)nbaum)

Zhang ZZ (1992) New algorithms for the system of linear equations and linear programming. Hong Kong Sino Tech Press, Hong Kong (In Chinese)

Wang PZ (2011) Cone-cutting: a variant representation of pivot in Simplex. Inf Technol Decis Mak 10(1):65–82CrossRef

Wang PZ, Ostermark R, Alex R, Tan SH (2001) Polyhedral representation of fuzzy linear bases. Soft Comput 5:208–214CrossRef

Pan PQ (2005) A revised dual projective pivot algorithm for linear programming. SIAM J Optim 16(1):49–68CrossRef

Klee V, Walkup DW (1967) The d-step conjecture for polyhedra of dimension d \(<\) 6. Acta Math 133:53–78CrossRef

10.

Terlaky T (2009) Algorithms and conjectures for linear optimization. In: A speech in the International Conference on Linear Programming, Hainan, China

11.

Chen HD, Pardalos PM, Saunders MA (1994) The simplex algorithm with a new primal and dual pivot rule. Oper Res Lett 16(3):121–127CrossRef

Titel: Discussions on Hirsch Conjecture and The Existence of Strongly Polynomial: Time Simplex Variants
verfasst von: Pei-Zhuang Wang
Publikationsdatum: 01.03.2014
Verlag: Springer Berlin Heidelberg
Erschienen in: Annals of Data Science / Ausgabe 1/2014
Print ISSN: 2198-5804
Elektronische ISSN: 2198-5812
DOI: https://doi.org/10.1007/s40745-014-0005-9

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Technik"

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 1/2014

Exact Solutions to the Capacitated Clustering Problem: A Comparison of Two Models

Heterogeneous Embedding via Aggregating Multiple Sources

Approximation of Irregular Geometric Data by Locally Calculated Univariate Cubic Spline Fits

Proposal of New Objective Measures for Mining Association Rules: Cannibalization and Unexpectedness

A New Nonlinear Multiregression Model Based on the Lower and Upper Integrals

Toward Extenics-Based Innovation Model on Intelligent Knowledge Management