4511
правок
Минимальная бисекция: различия между версиями
Перейти к навигации
Перейти к поиску
нет описания правки
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) Нет описания правки |
||
| Строка 106: | Строка 106: | ||
Если рассматривать более широкий контекст, в настоящее время существует мультипликативный разрыв в O(log n) между коэффициентом аппроксимации для задачи о минимальной бисекции и коэффициентом аппроксимации для задачи о разрезах с минимальным частным (таким образом, это соотношение актуально также для аппроксимации по двум критериям). Любопытно, можно ли сократить этот разрыв – | Если рассматривать более широкий контекст, в настоящее время существует мультипликативный разрыв в O(log n) между коэффициентом аппроксимации для задачи о минимальной бисекции и коэффициентом аппроксимации для задачи о разрезах с минимальным частным (таким образом, это соотношение актуально также для аппроксимации по двум критериям). Любопытно, можно ли сократить этот разрыв – например, при помощи алгоритма из [2], применив его вне подхода «черного ящика». | ||
Версия с вершинным разрезом задачи о минимальном разрезе определяется следующим образом. Цель состоит в разбиении вершин входного графа на множества V = A [ B [ S, где |S| насколько возможно мало, при соблюдении следующего ограничения: max fjAj; jBjg < n/2 и ни одно ребро не связывает множества A и B. Неизвестно, можно ли получить алгоритм аппроксимации с полилогарифмическим коэффициентом для решения этой задачи. Стоит отметить, что на тот же вопрос, касающийся версии задачи о минимальной бисекции для ориентированных графов, Фейгеи Яхалом дали отрицательный ответ [8]. | |||
== См. также == | |||
См. вводную часть статьи Ароры, Рао и Вазирани [2]. | |||
*'' [[Сепараторы в графах]] | |||
*'' [[Самое неплотное сечение]] | |||
== Литература == | |||
1. Alpert, C.J., Kahng, A. B.: Recent directions in netlist partition ing: a survey. Integr. VLSI J. 19(1-2), 1-81 (1995) | |||
2. Arora, S., Rao, S., Vazirani, U.: Expander flows, geometric embeddings, and graph partitionings. In: 36th Annual Symposium on the Theory of Computing, pp. 222-231, Chicago, June 2004 | |||
3. Berman, P., Karpinski, M.: Approximability of hypergraph minimum bisection. ECCC Report TR03-056, Electronic Colloquium on Computational Complexity, vol. 10(2003) | |||
4. Bui,T.N., Jones, C.: Finding good approximate vertex and edge partitions is NP-hard. Inform. Process. Lett. 42(3), 153-159 (1992) | |||
5. Coja-Oghlan, A.,Goerdt, A., Lanka, A., Schadlich, F.: Techniques from combinatorial approximation algorithms yield efficient algorithms for random 2k-SAT. Theor. Comput. Sci. 329(1-3), 1-45(2004) | |||
6. Feige, U., Krauthgamer, R.: A polylogarithmic approximation of the minimum bisection. SIAM Review 48(1), 99-130 (2006) (Previous versions appeared in Proceedings of 41st FOCS, 1999; and in SIAM J. Comput. 2002) | |||
8. Feige, U., Yahalom, O.: On the complexity of finding balanced oneway cuts. Inf. Process. Lett. 87(1), 1-5 (2003) | |||
7. Feige, U.: Relations between average case complexity and approximation complexity. In: 34th Annual ACM Symposium on the Theory of Computing, pp. 534-543, Montreal, May 19-21, | |||
2002 | |||
9. Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-completeness. W.H. Freeman and Company (1979) | |||
10. Karger, D.R.: Minimum cuts in near-linear time. J. ACM 47(1), 46-76 (2000) | |||
11. Kernighan, B.W., Lin, S.: An efficient heuristic procedure for partitioning graphs. Bell Syst. Tech. J. 49(2), 291-307 (1970) | |||
12. Khot, S.: Ruling out PTAS for graph Min-Bisection, Densest Subgraph and BipartiteClique. In:45th Annual IEEE Symposium on Foundations of Computer Science, pp. 136-145, Georgia Inst. of Technol., Atlanta 17-19Oct.2004 | |||
13. Klein, P., Plotkin, S.A., Rao, S.: Excluded minors, network decomposition, and multicommodity flow. In: 25th Annual ACM Symposium on Theory of Computing, pp. 682-690, San Diego, 1993 May 16-18 | |||
14. Leighton, T., Rao, S.: Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. J. ACM 46(6), 787-832, 29th FOCS, 1988 (1999) | |||
15. Lipton, R.J., Tarjan, R.E.: Applications of a planar separator theorem. SIAM J. Comput. 9(3), 615-627 (1980) | |||
16. Rosenberg, A.L., Heath, L.S.: Graph separators, with applications. Frontiers of Computer Science. Kluwer Academic/Plenum Publishers, New York (2001) | |||
17. Svitkina, Z., Tardos, Ё.: Min-Max multiway cut. In: 7th International workshop on Approximation algorithms for combinatorial optimization (APPROX), pp. 207-218, Cambridge, 2004 August 22-24 | |||