Biobjective optimization problems on matroids with binary costs

References

• Whitney H. On the abstract properties of linear dependence. Am J Math. 1935;57(3):509–533.
   Google Scholar
• Kung JPS. A source book in matroid theory. Boston: Birkhäuser; 1986.
   Google Scholar
• Oxley JG. Matroid theory. NJ: Oxford University Press; 1992.
   Google Scholar
• Ruzika S, Hamacher H. A survey on multiple objective minimum spanning tree problems. In: Lerner J, Wagner D, Zweig KA, editors. Algorithmics. Berlin, Heidelberg: Springer; 2009. p. 104–116. (Lecture Notes in Computer Science; vol. 5515/2009).
   Google Scholar
• Benabbou N, Perny P. On possibly optimal tradeoffs in multicriteria spanning tree problems. In: Walsh T, editor. Algorithmic decision theory; Cham: Springer International Publishing; 2015. p. 322–337.
   Google Scholar
• Zhou G, Gen M. Genetic algorithm approach on multi-criteria minimum spanning tree problem. Eur J Oper Res. 1999;114:141–152.
   Web of Science ®Google Scholar
• Knowles JD, Corne DW. A comparison of encodings andalgorithms for multiobjective minimum spanning tree problems. In: Proceedings of the IEEE Congress on Evolutionary Computation (CEC '01), Seoul, Korea (South). IEEE Press; 2001. p. 544–551.
   Google Scholar
• Neumann F, Witt C. Multi-objective minimum spanning trees. In: Neumann F, Witt C, editors. Bioinspired computation in combinatorial optimization. Berlin, Heidelberg: Springer; 2010. p. 149–159. (Natural Computing Series).
   Google Scholar
• Bossek J, Grimme C, Neumann F. On the benefits of biased edge-exchange mutation for the multi-criteria spanning tree problem. In: Proceedings of the 21th Genetic and Evolutionary Computation Conference (GECCO). Prague, Czech Republic: ACM; 2019. p. 516–523.
   Google Scholar
• Loera JAD, Haws DC, Lee J, et al. Computation in multicriteria matroid optimization. J Exp Algorithmics. 2010;14:8.
   Google Scholar
• Loera JAD, Haws DC, Lee J, et al. MOCHA – matroids optimization combinatorics heuristics and algorithms; 2009. Available from: https://github.com/coin-or/MOCHA.
   Google Scholar
• Grandoni F, Ravi R, Singh M, et al. New approaches to multi-objective optimization. Math Program. 2014;146:525–554.
   Web of Science ®Google Scholar
• Bazgan C, Ruzika S, Thielen C, et al. The power of the weighted sum scalarization for approximating multiobjective optimization problems. CoRR abs/1908.01181; 2019. Available from: http://arxiv.org/abs/1908.01181.
   Google Scholar
• Figueira JR, Fonseca CM, Halffmann P, et al. Easy to say they're hard, but hard to see they're easy – toward a categorization of tractable multiobjective combinatorial optimization problems. J Multi-Criteria Decis Anal. 2017;24:82–98.
   Web of Science ®Google Scholar
• Ehrgott M. On matroids with multiple objectives. Optimization. 1996;38(1):73–84.
   Google Scholar
• Hamacher HW, Ruhe G. On spanning tree problems with multiple objectives. Ann Oper Res. 1994;52:209–230.
   Google Scholar
• Bökler F, Ehrgott M, Morris C, et al. Output-sensitive complexity of multiobjective combinatorial optimization. J Multi-Criteria Decis Anal. 2017;24:25–36.
   Web of Science ®Google Scholar
• Bökler F. Output-sensitive complexity of multiobjective combinatorial optimization with an application to the multiobjective shortest path problem [dissertation]. Dortmund, Germany: TU Dortmund; 2018.
   Google Scholar
• Seipp F. On adjacency, cardinality, and partial dominance in discrete multiple ob- jective optimization [dissertation]. Kaiserslautern, Germany: TU Kaiserslautern; 2013.
   Google Scholar
• Gorski J, Klamroth K, Ruzika S. Connectedness of efficient solutions in multiple objective combinatorial optimization. J Optim Theory Appl. 2011;150:475–497.
   Web of Science ®Google Scholar
• Rendl F, Leclerc M. A multiply constrained matroid optimization problem. Discrete Math. 1988;73:207–212.
   Web of Science ®Google Scholar
• Brezovec C, Cornuéjols G, Glover F. A matroid algorithm and its application to the efficient solution of two optimization problems on graphs. Math Program. 1988;42:471–487.
   Web of Science ®Google Scholar
• Srinivas MA. Matroid optimization with generalized constraints. Discrete Appl Math. 1995;63:161–174.
   Web of Science ®Google Scholar
• Hamacher HW, Rendl F. Color constrained combinatorial optimization problems. Oper Res Lett. 1991;10:211–219.
   Web of Science ®Google Scholar
• Climaco JCN, Captivo ME, Pascoal MMB. On the bicriterion – minimal cost/minimal label – spanning tree problem. Eur J Oper Res. 2010;204:199–205.
   Web of Science ®Google Scholar
• Chang R, Leu SJ. The minimum labeling spanning trees. Inf Process Lett. 1997;63(5):277–282.
   Web of Science ®Google Scholar
• Gorski J, Ruzika S. On k-max optimization. Oper Res Lett. 2009;37(1):23–26.
   Web of Science ®Google Scholar
• Gorski J. Multiple objective optimization and implications for single objective optimization. Wuppertal, Germany: Shaker Verlag; 2010.
   Google Scholar
• Gabow HN, Tarjan RE. Efficient algorithms for a family of matroid intersection problems. J Algorithms. 1984;5:80–131.
   Web of Science ®Google Scholar
• Ehrgott M. Multicriteria optimization. Berlin, Heidelberg: Springer Verlag; 2005.
   Google Scholar
• Miettinen K. Nonlinear multiobjective optimization. Boston: Kluwer Academic Publishers; 1999.
   Google Scholar
• Brualdi RA. Comments on bases in dependence structures. Bull Aust Math Soc. 1969;1(2):161–167.
   Google Scholar
• Chankong V, Haimes YY. Multiobjective decision making: theory and methodology. New York: Elsevier Science Publishing; 1983.
   Google Scholar
• Gusfield D. Matroid optimization with the interleaving of two ordered sets. Discrete Appl Math. 1984;8(1):41–50.
   Web of Science ®Google Scholar
• Hotz M. generatespanningtrees(a); 2016. Matlab implementation for MST computation, MATLAB Central File Exchange, downloaded on February 19, 2020. Available from: https://www.mathworks.com/matlabcentral/fileexchange/53787-generatespanningtrees-a.
   Google Scholar
• Knuth DE. The art of computer programming. Boston: Pearson Education, Inc.; 2012. (Combinatorial Algorithms, Part 1; vol. 4A).
   Google Scholar
• Fernandes I, Goldbarg E, Maia S, et al. Empirical study of exact algorithms for the multi-objective spanning tree. Comput Optim Appl. 2020;75:561–605.
   Web of Science ®Google Scholar
• Schnepper T, Klamroth K, Puerto J, et al. A local analysis to determine all optimal solutions of p-k-max location problems on networks. Discrete Appl Math. 2021; 296:217–234.
   Web of Science ®Google Scholar
• Russell M. Laplacian matrices of graphs: a survey. Linear Algebra Appl. 1994;197-198:143–176.
   Web of Science ®Google Scholar
• Klamroth K, Wiecek M. Dynamic programming approaches to the multiple criteria knapsack problem. Nav Res Logist. 2000;47:57–76.
   Web of Science ®Google Scholar