Locally Defined Independence Systems on Graphs

• Item type: SIG Technical Reports(1)
• 公開日: 2023-01-12
• タイトル: Locally Defined Independence Systems on Graphs
• タイトル / 言語: en
• タイトル: Locally Defined Independence Systems on Graphs
• 言語: eng
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: Research Institute for Mathematical Sciences, Kyoto University
• 著者所属(英): en
• 著者所属(英): Research Institute for Mathematical Sciences, Kyoto University
• 著者名: Yuki, Amano
• 著者名(英): Yuki, Amano
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: The maximization for the independence systems defined on graphs is a generalization of combinatorial optimization problems such as the maximum b-matching, the unweighted MAX-SAT, the matchoid, and the maximum timed matching problems. In this paper, we consider the problem under the local oracle model to investigate the global approximability of the problem by using the local approximability. We first analyze two simple algorithms FixedOrder and Greedy for the maximization under the model, which shows that they have no constant approximation ratio. Here algorithms FixedOrder and Greedy apply local oracles with fixed and greedy orders of vertices, respectively. We then propose two approximation algorithms for the k-degenerate graphs, whose approximation ratios are α + 2k - 2 and αk, where α is the approximation ratio of local oracles. The second one can be generalized to the hypergraph setting. We also propose an (α + k)-approximation algorithm for bipartite graphs, in which the local independence systems in the one-side of vertices are k-systems with independence oracles.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: The maximization for the independence systems defined on graphs is a generalization of combinatorial optimization problems such as the maximum b-matching, the unweighted MAX-SAT, the matchoid, and the maximum timed matching problems. In this paper, we consider the problem under the local oracle model to investigate the global approximability of the problem by using the local approximability. We first analyze two simple algorithms FixedOrder and Greedy for the maximization under the model, which shows that they have no constant approximation ratio. Here algorithms FixedOrder and Greedy apply local oracles with fixed and greedy orders of vertices, respectively. We then propose two approximation algorithms for the k-degenerate graphs, whose approximation ratios are α + 2k - 2 and αk, where α is the approximation ratio of local oracles. The second one can be generalized to the hypergraph setting. We also propose an (α + k)-approximation algorithm for bipartite graphs, in which the local independence systems in the one-side of vertices are k-systems with independence oracles.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2023-AL-191, 号 5, p. 1-8, 発行日 2023-01-12
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8566
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会