Dlaczego matroidy? 50 lat teorii, 1935-1985

• Autorzy: Krystian Strzelec
• Języki publikacji: PL

Abstrakty

Matroidy to struktury kombinatoryczne, które, podobnie jak grafy, znajdują szerokie zastosowanie przy rozwiązywaniu problemów optymalizacji kombinatorycznej (OK). Analiza kombinatoryczna to matematyczne studium rozmieszczenia, grupowania, porządkowania czy wyboru pomiędzy pewnymi obiektami, zazwyczaj skończonymi co do ilości. Tradycyjnie matematycy zajmujący się kombinatoryką rozważali problemy istnienia i wyliczenia ilości pewnych kombinacji elementów o danych własnościach. Ostatnio nowy kierunek badań uzyskuje coraz bardziej rosnące znaczenie. To co najbardziej istotne sprowadza się do znalezienia optymalnych kombinacji spośród wszystkich możliwych, niezależnie od tego jak wielka jest ich ilość. Prawie zawsze prowadzi to do konieczności wyboru spośród ogromnej liczby możliwości. Problemy OK mogą być sformułowane jako odpowiednie zagadnienia programowania w liczbach całkowitych (PC). Ponieważ, jak dotąd, nie istnieje w dostatecznym stopniu satysfakcjonująca metoda (jak np. metoda sympleksowa dla zagadnień programowania liniowego, PL) rozwiązująca dowolne zadanie PC, znajdowanie rozwiązań optymalnych wielu problemów kombinatorycznych jest niemożliwe stosując procedury rozwiązywania zadań PC. Istnieje powszechna zgodność co do tego, że problem jest dobrze rozwiązywalny, jeśli istnieje dla niego algorytm ograniczony wielomianowo. Dla większości problemów OK algorytmów takich nie ma. (fragment tekstu)

Słowa kluczowe

PL

Kombinatoryka; Optymalizacja; Teoria optymalizacji; Grafy

EN

Combinatorial analysis; Optimalization; Optimization theory; Graphs

• Czasopismo: Zeszyty Naukowe. Seria 1 / Akademia Ekonomiczna w Poznaniu
• Rocznik: 1989
• Numer: nr 159 Prace Instytutu Cybernetyki Ekonomicznej
• Strony: 196--205

Twórcy

autor

Krystian Strzelec

Bibliografia

• Berge C. 1973, Graphs and Hypergranhs, North-Holland.
• Bixby R.E., Cunningham W.H. 1980, Converting Linear Programs to networks Problems. Math. OR 5.
• Christofides N. 1975, Graph Theory. An Algorithmic Approach. Academic Press.
• Dunstan P.D.J., Welsh D.J.A. 1973, A Greedy Algorithm for Solving a Certain Class of Linear Programmes. Math. Progr. 5, 338-353.
• Edmonds J. 1971, Matroids and the Greedy Algorithm. Math. Progr. 1, 127-136.
• Evans J.R., Jarvis J.J., Duke R.A. 1977, Graphic Matroids and the Multicommodity Transportation Problem. Math. Progr. 13, 323-328.
• Garfinkel R., Rao M. 1976, Bottleneck Linear Programming. Math. Progr. 11, 291-298.
• Glover P.,1975, New Results in Equivalent Integer Programming Formulations. Math. Progr. 8, 84-90.
• Gondran M., Minoux M. 1984, Graphs and Algorithms. J. Wiley.
• Griszuchin W.P. 1983, Submodularnyje zadaczi i ałgoritmy ich reszenija. Techniczeskaja Kibernetika. AN SSSR 1, 183-193.
• Hadley G. 1964, Nonlinear and Dynamic Programming, Addison-Wesley.
• Klee V. 1980, Combinatorial Optimization: What is the State of the Art. Math. O.R. 5, 1-26.
• Korbut A.A., Pinkelsztejn J.J. 1982, More on Independence Systems. Math. Operationsforsch. Statistik, Ser. Optimization 13, 349-58.
• Lawler, E.L. 1976, Combinatorial Optimization: Networks and Matroids. Holt, Rinehart and Winston.
• Magazine M.J., Nemhauser G.L., Trotter L.E., Jr. 1975, When the Greedy Solution Solves a Class of Knapsack Problems. Opns. Res. 23, 207-217.
• Nemhauser G.L., Wolsey L.A., Fisher M.L. 1978, An Analysis of Approximations for Maximizing Submodular Set Functions. Math. Progr. 14, 265-294.