Skip to main content
Springer Nature Link
Log in

Decreasing minimization on M-convex sets: background and structures

  • Full Length Paper
  • Series A
  • Published:
Mathematical Programming Submit manuscript

Abstract

The present work is the first member of a pair of papers concerning decreasingly-minimal (dec-min) elements of a set of integral vectors, where a vector is dec-min if its largest component is as small as possible, within this, the next largest component is as small as possible, and so on. This discrete notion, along with its fractional counterpart, showed up earlier in the literature under various names. The domain we consider is an M-convex set, that is, the set of integral elements of an integral base-polyhedron. A fundamental difference between the fractional and the discrete case is that a base-polyhedron has always a unique dec-min element, while the set of dec-min elements of an M-convex set admits a rich structure, described here with the help of a ‘canonical chain’. As a consequence, we prove that this set arises from a matroid by translating the characteristic vectors of its bases with an integral vector. By relying on these characterizations, we prove that an element is dec-min if and only if the square-sum of its components is minimum, a property resulting in a new type of min-max theorems. The characterizations also give rise, as shown in the companion paper, to a strongly polynomial algorithm, and to several applications in the areas of resource allocation, network flow, matroid, and graph orientation problems, which actually provided a major motivation to the present investigations. In particular, we prove a conjecture on graph orientation.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2

Similar content being viewed by others

References

  1. Ahuja, R.K., Hochbaum, D.S., Orlin, J.B.: A cut-based algorithm for the nonlinear dual of the minimum cost network flow problem. Algorithmica 39, 189–208 (2004)

    Article  MathSciNet  Google Scholar 

  2. Arnold, B.C., Sarabia, J.M.: Majorization and the Lorenz Order with Applications in Applied Mathematics and Economics, Springer International Publishing, Cham (2018), (1st edn., 1987)

  3. Bokal, D., Brešar, B., Jerebic, J.: A generalization of Hungarian method and Hall’s theorem with applications in wireless sensor networks. Discrete Appl. Math. 160, 460–470 (2012)

  4. Borradaile, G., Iglesias, J., Migler, T., Ochoa, A., Wilfong, G., Zhang, L.: Egalitarian graph orientations. J. Graph Algorithms Appl. 21, 687–708 (2017)

    Article  MathSciNet  Google Scholar 

  5. Borradaile, G., Migler, T., Wilfong, G.: Density decompositions of networks. J. Graph Algorithms Appl. 23, 625–651 (2019)

    Article  MathSciNet  Google Scholar 

  6. Edmonds, J.: Submodular functions, matroids and certain polyhedra. In: Guy, R., Hanani, H., Sauer, N., Schönheim, J. (eds.) Combinatorial Structures and Their Applications, pp. 69–87. Gordon and Breach, New York (1970)

    Google Scholar 

  7. Federgruen, A., Groenevelt, H.: The greedy procedure for resource allocation problems: necessary and sufficient conditions for optimality. Oper. Res. 34, 909–918 (1986)

    Article  MathSciNet  Google Scholar 

  8. Frank, A.: On the orientation of graphs. J. Combin. Theory Ser. B 28, 251–261 (1980)

    Article  MathSciNet  Google Scholar 

  9. Frank, A.: Connections in Combinatorial Optimization. Oxford University Press, Oxford (2011)

    MATH  Google Scholar 

  10. Frank, A., Murota, K.: Discrete decreasing minimization, Part II: Views from discrete convex analysis. arXiv: 1808.08477 (2018)

  11. Frank, A., Murota, K.: Decreasing minimization on M-convex sets: Algorithms and applications. Mathematical Programming, published online (October 15, 2021). https://doi.org/10.1007/s10107-021-01711-5

  12. Frank, A., Murota, K.: A discrete convex min-max formula for box-TDI polyhedra. Mathematics of Operations Research, to appear. arXiv:2007.03507

  13. Frank, A., Murota, K.: Fair integral flows. Submitted for publication. arXiv: 1907.02673v3 (2020)

  14. Frank, A., Murota, K.: Fair integral submodular flows. Submitted for publication. arXiv: 2012.07325 (2020)

  15. Fujishige, S.: Lexicographically optimal base of a polymatroid with respect to a weight vector. Math. Oper. Res. 5, 186–196 (1980)

    Article  MathSciNet  Google Scholar 

  16. Fujishige, S.: Submodular Functions and Optimization, 2nd edn. Annals of Discrete Mathematics 58. Elsevier, Amsterdam (2005)

  17. Fujishige, S.: Theory of principal partitions revisited. In: Cook, W., Lovász, L., Vygen, J. (eds.) Research Trends in Combinatorial Optimization, pp. 127–162. Springer, Berlin (2009)

    Chapter  Google Scholar 

  18. Ghodsi, A., Zaharia, M., Shenker, S., Stoica, I.: Choosy: Max-min fair sharing for datacenter jobs with constraints. In: EuroSys ’13 Proceedings of the 8th ACM European Conference on Computer Systems, pp. 365–378, ACM New York, NY (2013)

  19. Groenevelt, H.: Two algorithms for maximizing a separable concave function over a polymatroid feasible region. Eur. J. Oper. Res. 54, 227–236 (1991)

    Article  Google Scholar 

  20. Harada, Y., Ono, H., Sadakane, K., Yamashita, M.: Optimal balanced semi-matchings for weighted bipartite graphs. IPSJ Digital Courier 3, 693–702 (2007)

    Article  Google Scholar 

  21. Harvey, N.J.A., Ladner, R.E., Lovász, L., Tamir, T.: Semi-matchings for bipartite graphs and load balancing. J. Algorithms 59, 53–78 (2006)

    Article  MathSciNet  Google Scholar 

  22. Hochbaum, D.S.: Solving integer programs over monotone inequalities in three variables: a framework for half integrality and good approximations. Eur. J. Oper. Res. 140, 291–321 (2002)

    Article  MathSciNet  Google Scholar 

  23. Hochbaum, D.S.: Complexity and algorithms for nonlinear optimization problems. Ann. Oper. Res. 153, 257–296 (2007)

    Article  MathSciNet  Google Scholar 

  24. Hochbaum, D.S., Hong, S.-P.: About strongly polynomial time algorithms for quadratic optimization over submodular constraints. Math. Program. 69, 269–309 (1995)

    Article  MathSciNet  Google Scholar 

  25. Ibaraki, T., Katoh, N.: Resource Allocation Problems: Algorithmic Approaches. MIT Press, Boston (1988)

    MATH  Google Scholar 

  26. Katoh, N., Ibaraki, T.: Resource allocation problems. In: Du, D.-Z., Pardalos, P.M. (eds.) Handbook of Combinatorial Optimization, vol. 2, pp. 159–260. Kluwer Academic Publishers, Boston (1998)

    Google Scholar 

  27. Katoh, N., Shioura, A., Ibaraki, T.: Resource allocation problems. In: Pardalos, P.M., Du, D.-Z., Graham, R.L. (eds.) Handbook of Combinatorial Optimization, vol. 5, 2nd edn., pp. 2897–2988. Springer, Berlin (2013)

    Chapter  Google Scholar 

  28. Katrenič, J., Semanišin, G.: Maximum semi-matching problem in bipartite graphs. Discussiones Mathematicae Graph Theory 33, 559–569 (2013)

    Article  MathSciNet  Google Scholar 

  29. Levin, A., Onn, S.: Shifted matroid optimization. Oper. Res. Lett. 44, 535–539 (2016)

    Article  MathSciNet  Google Scholar 

  30. Lovász, L.: Submodular functions and convexity. In: Bachem, A., Grötschel, M., Korte, B. (eds.) Mathematical Programming-The State of the Art, pp. 235–257. Springer, Berlin (1983)

    Chapter  Google Scholar 

  31. Marshall, A.W., Olkin, I., Arnold, B.C.: Inequalities: Theory of Majorization and Iis Applications, 2nd edn. Springer, New York (2011), (1st edn., 1979)

  32. Maruyama, F.: A unified study on problems in information theory via polymatroids. Graduation Thesis, University of Tokyo, Japan (1978) (in Japanese)

  33. Megiddo, N.: Optimal flows in networks with multiple sources and sinks. Math. Program. 7, 97–107 (1974)

    Article  MathSciNet  Google Scholar 

  34. Megiddo, N.: A good algorithm for lexicographically optimal flows in multi-terminal networks. Bull. Am. Math. Soc. 83, 407–409 (1977)

    Article  MathSciNet  Google Scholar 

  35. Murota, K.: Discrete convex analysis. Math. Program. 83, 313–371 (1998)

    Article  MathSciNet  Google Scholar 

  36. Murota, K.: Discrete Convex Analysis. Society for Industrial and Applied Mathematics, Philadelphia (2003)

    Book  Google Scholar 

  37. Nagano, K.: On convex minimization over base polytopes. In: Fischetti, M., Williamson, D.P. (eds.): Integer Programming and Combinatorial Optimization. Lecture Notes in Computer Science, vol. 4513, pp. 252–266 (2007)

  38. Tamir, A.: Least majorized elements and generalized polymatroids. Math. Oper. Res. 20, 583–589 (1995)

    Article  MathSciNet  Google Scholar 

Download references

Acknowledgements

We are grateful to the six authors of the paper by Borradaile et al. [4] because that work triggered the present research (and this is so even if we realized later that there had been several related works). We thank S. Fujishige and S. Iwata for discussion about the history of convex minimization over base-polyhedra. We also thank A. Jüttner and T. Maehara for illuminating the essence of the Newton–Dinkelbach algorithm. J. Tapolcai kindly drew our attention to engineering applications in resource allocation. Z. Király played a similar role by finding an article which pointed to a work of Levin and Onn on decreasingly minimal optimization in matroid theory. We are also grateful to M. Kovács for drawing our attention to some important papers in the literature concerning fair resource allocation problems. Special thanks are due to T. Migler for her continuous availability to answer our questions concerning the paper [4] and the work by Borradaile, Migler, and Wilfong [5], which paper was also a prime driving force in our investigations. We are grateful to B. Shepherd and K. Bérczi for their advice that led to restructuring our presentation appropriately. We are also grateful to an anonymous referee of the paper whose strategic suggestions were particularly important to shape the final form of our work. This research was supported through the program “Research in Pairs” by the Mathematisches Forschungsinstitut Oberwolfach in 2019. The two weeks we could spend at Oberwolfach provided an exceptional opportunity to conduct particularly intensive research. The research was partially supported by the National Research, Development and Innovation Fund of Hungary (FK_18) – No. NKFI-128673, and by CREST, JST, Grant Number JPMJCR14D2, Japan, and JSPS KAKENHI Grant Numbers JP26280004, JP20K11697.

Author information

Author notes

  1. Kazuo Murota

    Present address: The Institute of Statistical Mathematics, Tokyo, 190-8562, Japan

Authors and Affiliations

  1. MTA-ELTE Egerváry Research Group, Department of Operations Research, Eötvös University, Pázmány P. s. 1/c, 1117, Budapest, Hungary

    András Frank

  2. Department of Economics and Business Administration, Tokyo Metropolitan University, Tokyo, 192-0397, Japan

    Kazuo Murota

Authors
  1. András Frank
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Kazuo Murota
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Kazuo Murota.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

The research was partially supported by the National Research, Development and Innovation Fund of Hungary (FK_18) – No. NKFI-128673. The research was supported by CREST, JST, Grant Number JPMJCR14D2, Japan, and JSPS KAKENHI Grant Numbers JP26280004, JP20K11697.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Frank, A., Murota, K. Decreasing minimization on M-convex sets: background and structures. Math. Program. 195, 977–1025 (2022). https://doi.org/10.1007/s10107-021-01722-2

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10107-021-01722-2

Keywords

Mathematics Subject Classification

Search

Navigation