Симметрии многогранника системы независимости и их применение для решения задачи об упаковке множества
Диссертация
Эксперименты проводились на задаче об упаковке множества (первая и вторая серии экспериментов) и задаче о наибольшем независимом множестве вершин (третья и четвертая серии). В общей сложности было решено 185 задач об упаковке множества и 196 задач' о наибольшем независимом множестве вершин графа. Из полученных результатов вытекает, что предложенные в работе приближенные алгоритмы имеют хорошую… Читать ещё >
Список литературы
- Ашманов С.А. Введение в математическую экономику. М.: Наука, 1984.
- Береснев В.Л., Гимади Э. Х., Дементьев В. Т. Экстремальные задачи стандартизации. Новосибирск: Наука, 1978.
- Болоташвили Г. Г., Ковалев М. М. Частично упорядоченный многогранник. Тез. докл. VII конференции «Проблемы теоретической кибернетики». Горький. 1988.
- Брёнстед А. Введение в теорию выпуклых многогранников. -М.: Мир. 1988.
- Вьялицпн A.A., Панченко К. А. Применение теории групп для решения комбинаторных задач. Петропавловск: Северо-Казахстанский университет, 199−5.
- Глебов Н.И. Базисные системы и задача минимизации на пересечении базисных систем. // Управляемые системы. Новосибирск: ИМ СО АН СССР, 1984. Вып. 25. С. 58−67.
- Гранже М., Менсьё Ф. OS/2. Принципы построения и установка. -М.: Мир. 1991.
- Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.
- Дейтл Г. Введение в операционные системы (в 2-х томах). ~ М.: Мир, 1987.
- Емеличев В.А., Ковалев М. М., Кравцов М. К. Многогранники, графы, оптимизация. М.: Наука, 1981.
- Емеличев В.А. и др. Лекции по теории графов. М.: Наука, 1990.
- Заблоцкая O.A., Колоколов A.A. Вполне регулярные отсечения в булевом программировании. // Управляемые системы. Новосибирск: ИМ СО АН СССР, 1983. Вып. 23. С. 55−63.
- Заозерская ЛА. Некоторые гибридные алгоритмы для задачи о покрытии. // Тез. докл. Х-ой Всероссийской конференции «Математическое программирование и приложения». Екатеринбург: УрО РАН, 1997. С. 100.
- Ильев В.П. Оценка погрешности градиентного алгоритма для систем, независим, ости. // Дискретный анализ и исследование операций. 1996. Т.З. No.l. С. 9−22.
- Колоколов A.A. Методы дискретной оптимизации. Учебное пособие. Омск: ОмГУ, 1984.
- Колоколов A.A. Регулярные разбиения и отсечения в целочисленном программировании. // Сиб. журнал, исследования операций. 1994. N.2. С. 18−39.
- Корбут A.A., Финкельштейн Ю. Ю. Дискретное программирование.- М: Наука. 1969.
- Кристофидес Н. Теория графов. Алгоритмический подход. ~ М.: Мир, 1978.
- Коэн Л.Дж. Анализ и разработка операционных систем. М.: Наука, 197−5.
- Кузюрин H.H. Полиномиальный в среднем алгоритм в целочисленном линейном программировании. // Сибирский журнал: исследования операций. Новосибирск: ИМ СО РАН, 1994. Том 1, N.3. С. 38−48.
- Лотов A.B. Введение в экономико-математическое моделирование.- М.: Наука, 1984.
- Пападпмитриу X., Стайнглиц К. Комбинаторная оптимизация. -М.: Мир, 1985.
- Сайко И.В. Исследование мощности L-накрытий некоторых задач о покрытии. // Дискретная оптимизация и анализ сложных систем. Новосибирск: ВЦ СО АН СССР, 1989. С. 76−97.
- Сергиенко И.В. Математические модели и методы решения задач, дискретной оптимизации. Киев: Наук. думка, 1988.
- Симанчёв Р.Ю. Линейные симметрии многогранника паросочета-ний и автоморфизмы графа. // Вестник Омского университета. 1996. N.1. С. 18−20.
- Симанчёв Р.Ю. О ранговых неравенствах, порождающих фасеты многогранника связных k-факторов. // Дискретный анализ и исследование операций. Новосибирск: ИМ СО РАН, 1996. Т. З, N.3. С. 84 110.
- Симанчёв Р.Ю. Структура нецелочисленных вершин релаксации многогранника к-факторов. // Математические структуры и моделирование. Омск: ОмГУ, 1998. Вып.1. С. 20−26.
- Симанчёв Р.Ю. Смежность вершин многогранника к-факторов. // Математические структуры и моделирование. Омск: ОмГУ, 1998. Вып.2. С. 39−50.
- Симанчёв Р.Ю. Линейные симметрии многогранника паросочета-ний. // Тез. Второго сибирского Конгресса по индустриальной и прикладной математике. Новосибирск: ИМ СО РАН, 1996. С. 125.
- Симанчёв Р.Ю. Группа линейных симметрии многогранника Ъ-факторов. // Тез. межд. конф. «Проблемы оптимизации и экономический приложения"'. Омск, июль, 1997. С. 143.
- С’хрейвер А. Теория линейного и целочисленного программирования (в 2-х томах). М.: Мир, 1991.
- Харари Ф. Теория графов. М.: Мир. 1973.
- Хоар Ч. Взаимодействующие последовательные процессы. -М.: Мир, 1989.
- Хорошевский В.Г. Инж:енерный анализ функционирования вычислительных машин и систем. М.: Радио и связь, 1987.•35. Червяков О. В. Линейные симметрии, и автоморфизмы матроида. // Фундаментальная и прикладная математика. Омск: ОмГУ, 1994. С. 81−89.
- Червяков О.В. Аффинные преобразования матроида. // Тез. докл. Второго Сибирского конгресса по прикладной и индустриальной математике. Новосибирск: ИМ СО РАН, 1996. С. 127.
- Червяков О.В. Понижение размерности оптимизационной задачи на системе независимости. // Тез. докл. Х-ой Всероссийской конференции «Математическое программирование и приложения». Екатеринбург: УрО РАН, 1997. С. 229.
- Червяков О.В. Алгоритм нахождения симметрии многогранника системы независимости. // Тез. докл. Международной конференции «Проблемы оптимизации и экономические приложения». Омск: ОмГУ, 1997. С. 166.
- Червяков О.В. Симметрии многогранника системы независим, ости. // Вестник Омского университета. Омск, 1997. N.-3. С. 18−20.
- Червяков О.В. Симметрии многогранника системы независимости со сдвигом единичной мощности. // Материалы Международной Сибирской конференции по исследованию операций. Новосибирск: ИМ СО РАН, 1998. С. 70.
- Червяков О.В. Аффинные симметрии многогранника системы независимости. // Математические структуры и моделирование. Омск: ОмГУ, 1998. Вып.1. С. 27−32.
- Червяков О.В. Понижение размерности задачи об упаковке множества. // Тез. докл. XI-ой Всероссийской конференции «Математическое программирование и приложения». Екатеринбург: УрО РАН, 1999. С. 279.
- Червяков О.В. Аффинные симметрии многогранника системы независимости с единичным сдвигом. // Дискретный анализ и исследование операций. Новосибирск, 1999. Серия 1, Том 6. N.2. С. 82−96.
- Червяков О.В. Алгоритмы решения задачи об упаковке множества с использованием симметрии многогранника. Препринт № 1. Омск: Омский госуниверситет, кафедра мат. моделирования. 2000.
- Шевченко В.Н. Качественные вопросы целочисленного программирования. М.: Наука. 1995.
- Arkin Е.М., Hassin R. On local search for weighting k-.set packing. // ESA'97, LNCS 1284. 1997. P. 13−22.
- Bafna V., Narayanan B.O., Ravi R. Non-overlapmg local alignments (weighted independent sets of axis parallel rectangles). // WADS'95, LNCS 955, 1995. P. 506−517.
- Baker B.S. Approximation algorithms for NP-comphte problems on planar graphs. // J. ACM, 41, 1994. P. 153−180.
- Balas E. Project scheduling with resource contramts. Applications of mathematical programming techniques. Beale Ed.,. English Universities Press. London, 1970.
- Balas E., Yu C.S. Finding a Maximum Clique in an Arbitrary Graph. // SIAM J. Comput. 15(4). 1986. P. 1054−1068.
- Balas E., Xue J. Weighted and Unweighted Maximum Clique Algorithms with Upper Boud. s from, Fractional Coloring. // Algorithmica, 15. 1996. P. 397−412.
- Balas E., Niehaus W. Optimized Crossover-Based Genetic Algorithms for the Maximum Cardinality and Maximum Weight Clique Problems. // Journal of Heuristics, 4. 1998. P. 107−122.
- Bar-Yehuda R. One for the Price Two: A Unified Approach for Approximating Covering Problems. Technion. Computer Science Depatment. Technion Report CSS0920, 1997.
- Beineke LAV., Pippert R.E.Prorerties and characterizations of k-trees. // Mathematica, 18. 1971. P. 141−151.
- Bellmore M. Greenberg H., Jarviss J. Multi-commodity disconnecting sets. // Man. Sei. 16. 1970. P. 427.
- Bellmore M. Ratliff B.D. Optimal defense of multi-commodity networks. // Man. Sei. 18. 1971. P. 174.
- Bolotashvili G., Girlich E., Kovalev M. New Facets of the Linear Ordering Polytope. Preprint Nr. 15. Otto-von-Guericke-Universitat Magdeburg. Fakultat fur Mathematik, 1995.
- Boppana R.B. Halldorsson M.M. Approximating maximum independen-dent sets by excluding subgraphs. // BIT, 32(2), June 1992. P. 180−196.
- Chvatal V. A greedy heuristic for the set-covering problem,. // Math, of Oper. Res., 4(3), 1979. P. 233−235.
- Chvatal V. On Certain Polytopes Associated with Graphs. // .Journal of Combinatorial Theory (B). 18, 1975. P. 138−154.
- Clarkson K., 4 modification of the greedy algorithm for the vertex cover. // Info. Proc. Lett., 16, 1983. P. 23−25.
- Conforti M., Laurent M. On the facial structure of independence system polyhedra. // Math, of Operations Research. 1988, V.13, N.4. P. 543−555.
- Cook W., Pulleyblank W.R. Linear systems for constrained matching problems. // Math, of Operations Research. 1987. ?.12, N.l. P. 97−120.
- Dijkstra E.W. Cooperating Sequential Processes. Technological University. Eindhoven, The Netherlandss, 1965.
- Edmonds J. Matroids and the greedy algorithm. // Math. Programming, 1971. V.13. N.2. P. 127−136.
- Edmonds J. Maximum mathching and a polyhedron with 0.1-vertices. // Journal of Reserch of the National Bureau of Standarts B. 1965. P. 125 130.
- Edmonds J. Johnson E.L. Mathching: a well-solved class of integer liner programs. // Ed. by R. Gay, H. Hanani, N. Sauer and J. Sohonheim, Combinatorial sstructures and their applications. Gordon and Beach. New York, 1970. P. 89−92.
- Eremeev A.V. Some Approximate Algorithms for the Vertex Cover Problem. // Book of Abstr. of SOR'99. Otto-von-Guerike-Universitat Magdeburg, 1999. P. 46.
- Freeman D.R., Jucker The line balancing problem. // J. of Industrial Engineering. 18. 1967. P. 361.
- Gamble A.B., Pulleyblank W.R. Forest Covers and a Polyhedral Intersection Theorem,. // Mathimatical Programming, 1989. P. 49−58.
- Garraghan R., Parclalos P.M. An exact algorithm for the maximum clique problem. // Operation Research Letters, 9, 1990. P. 375−382.
- Grotshel M., Holland 0. Solution of lage-scale symmetric travelling salesman problem,. // Math, of Operation Reserch, 1986. V. ll, N.4. P. 537−569.7.3. Hastacl .J. Clique is hard to approximation within n16. // FOCS'96, 1996. P. 627−636.
- Halldorsson M.M., Radhakrishnan J. Greed is good: Approximating independent sets in sparse and bounded-degree graphs. // Algorithmica, 18, 1997. P. 145−163.
- Halldorsson M.M. Approximation via partitioning. Res. Report ISS-RR-95-0003 °F, Japan Adv. Inst, of Sei. and Tech., Mar. 1995.
- Halldorsson M.M. Approximation of independents sets in graphs. A survey paper, from APPROX. 1998.
- Hochbaum D.S. Efficient bounds for the stable set, vertex cover, and set packing problems. // Disc. Applied Math., 6, 1983. P. 243−254.
- Hochbaum D.S. Approximating covering and packing problems: set cover, vertex cover, independent set, and related problems. Chapter 3 in Approximation Algorithms for NP-Hard Problems. PWS Publishing Company. 1996. P. 94−143.
- Johnson D.S. Approximation algorithms for combinatorial problems. // J. of Comput. Syst. Sei., 9, 1974. P. 256−278.
- Johnson D.S., Trick M.A. Introduction to the Second DIM ACS Challenge: Clique, Colloring, and Satisfiability. // DIMACS Series in Discrete Math, and Theoretical Comp. Sei., Vol.26, 1995. P. 1−10.
- Karpinski M., Zelikovsky A. Approximating dense cases of covering problems ECCC Technical report TR 97−001, 1997.82. iNemhauser G., Trotter L.E. Vertex packings: structural properties and algorithm, s. // Mathematical Programming, 8, 1975. P. 232−248.
- Pardalos P., Xue J. The maximum clique problem. // J. of Global Optimization, 4, 1994. P. 301−328.
- Paschos V.T. A survey of approximately optimal solutions to some covering and packing problemss. // ACM Computing Surveys, 29(2), June 1997. P. 171−209'.
- Rutman R.A. An Althorithm for placement of inter-connected elements based on minimum wire length. // Proc. of AFIPS Conf. 20, 1964. P. 477.
- Salveson M.E. The assembly line balancing problem,. // J. of Industrial Engineering. 6, 1955. P. 18.106
- Simanchev R.Yu. The Sup-port inequalities and facets of combinatorial polytopes. // Intern, conf. «Optimal Discrete Structures and Algorithms», Rostock, Sept., 1997. P. 62.
- Soriano P., Gendreau M. Solving the Maximum Clique Problem. Using a Tabu-Search Approach. // Annals of Operations Research, 41, 1993. P. 385−403.
- Steinberg L. The background wiring problem- a placement algorithm. // J. of SIAM (Review). 3. 1961. P. 37.