日本語
 
User Manual Privacy Policy ポリシー/免責事項 連絡先
  詳細検索ブラウズ

アイテム詳細


公開

成果報告書

Combinatorial Persistency Criteria for Multicut and Max-Cut

MPS-Authors
/persons/resource/persons201523

Lange,  Jan-Hendrik
Computer Vision and Multimodal Computing, MPI for Informatics, Max Planck Society;

/persons/resource/persons98382

Andres,  Bjoern
Computer Vision and Multimodal Computing, MPI for Informatics, Max Planck Society;

/persons/resource/persons221924

Swoboda,  Paul
Computer Vision and Multimodal Computing, MPI for Informatics, Max Planck Society;

URL
There are no locators available
フルテキスト (公開)

arXiv:1812.01426.pdf
(プレプリント), 238KB

付随資料 (公開)
There is no public supplementary material available
引用

Lange, J.-H., Andres, B., & Swoboda, P. (2018). Combinatorial Persistency Criteria for Multicut and Max-Cut. Retrieved from http://arxiv.org/abs/1812.01426.


引用: http://hdl.handle.net/21.11116/0000-0002-A8E2-1
要旨
In combinatorial optimization, partial variable assignments are called persistent if they agree with some optimal solution. We propose persistency criteria for the multicut and max-cut problem as well as fast combinatorial routines to verify them. The criteria that we derive are based on mappings that improve feasible multicuts, respectively cuts. Our elementary criteria can be checked enumeratively. The more advanced ones rely on fast algorithms for upper and lower bounds for the respective cut problems and max-flow techniques for auxiliary min-cut problems. Our methods can be used as a preprocessing technique for reducing problem sizes or for computing partial optimality guarantees for solutions output by heuristic solvers. We show the efficacy of our methods on instances of both problems from computer vision, biomedical image analysis and statistical physics.