http://swrc.ontoware.org/ontology#TechnicalReport
On Tractable Problems of Diversity Optimization
en
Nagoya University
Kyoto University
National Institute of Informatics
Kyoto University
Nagoya University
Tesshu Hanaka
Yasuaki Kobayashi
Kazuhiro Kurita
See Woo Lee
Yota Otachi
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.
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-183
1
1-6
2021-04-30
2188-8566