Document Type: Research Paper

Authors

1 Department of Mathematics, Shahed University, Tehran, Iran.

2 Department of Computer Science, Shahed University, Tehran, Iran.

Abstract

Submodularity is an important  property of set functions with deep theoretical results  and various  applications. Submodular systems appear in many applicable area, for example machine learning, economics, computer vision, social science, game theory and combinatorial optimization.  Nowadays submodular functions optimization has been attracted by many researchers.  Pendant pairs of a symmetric submodular system  play  essential role  in finding a minimizer of this system.  In this paper,  we investigate some relations between pendant  pairs of  a  submodular  system and pendant pairs of its contractions. For a symmetric submodular system $\left(V,f\right)$ we construct a suitable sequence of $\left|V\right|-1$ pendant pairs of its contractions. By using this sequence, we present some properties of the system and its contractions. Finally, we prove some results about the minimizers of a posimodular function.

Keywords

[1] D. Dadush,  L.A. V'egh, and G. Zambelli, Geometric rescaling algorithms for submodular function minimization, in: Proc. 29th Annual ACM-SIAM Symposium on Discrete Algorithms, New Orleans, Louisiana, USA, 2018, 832-848.

[2] S. Fujishige,  Submodular functions and optimization, Elsevier., Amesterdam, 2005.

[3] M.X. Goemans and J.A. Soto, Algorithms for symmetric submodular function minimization under hereditary constraints and generalizations, SIAM J. Discrete Math., 27 (2013), pp. 1123-1145.

[4] M. Gr"otschel, L. Lov'asz, and A. Schrijver,  The ellipsoid method and its consequences in combinatorial optimization, Combinatorica., 1 (1981), pp. 169-197.

[5] M. Gr"otschel, L. Lov'asz, and A. Schrijver, Geometric algorithms and combinatorial optimization, Springer-Verlag., Berlin Heidelberg, 2012.

[6] S. Hanifehnezhad and A. Dolati, Gomory Hu Tree and Pendant Pairs of a Symmetric Submodular System, Lecture Notes in Comput. Sci., 10608  (2017), pp. 26-33.

[7] S. Iwata, L. Fleischer, and S. Fujishige, A combinatorial strongly polynomial algorithm for minimizing submodular functions, J. ACM., 48 (2001), pp. 761-777.

[8] S. Jegelka and J. Bilmes,  Cooperative cuts for image segmentation, Technical Report, University of Washington, Seattle,  2010.

[9] A. Krause and D. Golovin,  Submodular function maximization, in: Tractability: Practical Approaches to Hard Problems, Cambridge Univ. Press., Cambridge, 2014, 71-104.

[10] Y.T. Lee, A. Sidford, and S.C. Wong, A faster cutting plane method and its implications for combinatorial and convex optimization, in: Foundations of Computer Science (FOCS), 2015 IEEE 56th Annual Symposium, Berkeley, California, 2015,  1049-1065.

[11] S.T. McCormick,  Submodular function minimization, Handbooks Oper. Res. Management Sci., 12 (2005), pp. 321-391.

[12] H. Nagamochi,  Minimum degree orderings, Algorithmica., 56 (2010), pp. 17–34.

[13] H. Nagamochi and T. Ibaraki, A note on minimizing submodular functions, Inform. Process. Lett., 67 (1998), pp. 239-344.

[14] N. Nisan,  T. Roughgarden, E. Tardos, and  V.V. Vazirani,  Algorithmic game theory, Cambridge Univ. Press., New York, USA, 2007.

[15] J.B. Orlin,  A faster strongly polynomial time algorithm for submodular function minimization, Math. Program., 118 (2009), pp. 237-251.

[16] M. Queyranne,  Minimizing symmetric submodular functions, Math. Program., 82 (1998), pp. 3-12.

[17] A. Schrijver,  A combinatorial algorithm minimizing submodular functions in strongly polynomial time, J. Combin. Theory Ser. B., 80 (2000), pp. 346-355.

[18] A. Schrijver, Combinatorial optimization: polyhedra and efficiency, Springer-Verlag., Berlin Heidelberg, 2003.
 
[19] D.M. Topkis, Supermodularity and complementarity, Princeton Univ. Press., Princeton, 2011.