2024-02-26T23:35:00Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:002109772023-04-27T10:00:04Z01164:02592:10486:10582
On Tractable Problems of Diversity OptimizationOn Tractable Problems of Diversity Optimizationenghttp://id.nii.ac.jp/1001/00210871/Technical Reporthttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=210977&item_no=1&attribute_id=1&file_no=1Copyright (c) 2021 by the Information Processing Society of JapanNagoya UniversityKyoto UniversityNational Institute of InformaticsKyoto UniversityNagoya UniversityTesshu, HanakaYasuaki, KobayashiKazuhiro, KuritaSee, Woo LeeYota, OtachiFinding diverse solutions in combinatorial problems recently has received some attention. In this paper we study the following type of problems: given an integer k, the problem asks for k solutions such that the sum of pairwise Hamming distances between these solutions is maximized. We investigate the tractability of the “diverse version” of several classical combinatorial problems, such as finding bases of matroids, arborescences in directed graphs, bipartite matchings, shortest st-paths in directed graphs, and minimum cuts of undirected graphs.Finding diverse solutions in combinatorial problems recently has received some attention. In this paper we study the following type of problems: given an integer k, the problem asks for k solutions such that the sum of pairwise Hamming distances between these solutions is maximized. We investigate the tractability of the “diverse version” of several classical combinatorial problems, such as finding bases of matroids, arborescences in directed graphs, bipartite matchings, shortest st-paths in directed graphs, and minimum cuts of undirected graphs.AN1009593X研究報告アルゴリズム（AL）2021-AL-1831162021-04-302188-85662021-04-27