Аноним

Минимальная бисекция: различия между версиями

Материал из WEGA
нет описания правки
Нет описания правки
Строка 106: Строка 106:




Если рассматривать более широкий контекст, в настоящее время существует мультипликативный разрыв в O(log n) между коэффициентом аппроксимации для задачи о минимальной бисекции и коэффициентом аппроксимации для задачи о разрезах с минимальным частным (таким образом, это соотношение актуально также для аппроксимации по двум критериям). Любопытно, можно ли сократить этот разрыв – наприме, при помощи алгоритма из [2], применив его вне подхода «черного ящика».
Если рассматривать более широкий контекст, в настоящее время существует мультипликативный разрыв в 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
4551

правка