Optimal Balanced Semi-Matchings for Weighted Bipartite Graphs

• Item type: Journal(1)
• 公開日: 2007-10-15
• タイトル: Optimal Balanced Semi-Matchings for Weighted Bipartite Graphs
• タイトル / 言語: en
• タイトル: Optimal Balanced Semi-Matchings for Weighted Bipartite Graphs
• 言語: eng
• キーワード / 主題Scheme: Other
• キーワード / 主題: 論文
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• その他タイトル / その他のタイトル: アルゴリズム理論
• 著者所属: Graduate School of Information Science and Electrical Engineering Kyushu University
• 著者所属: Graduate School of Information Science and Electrical Engineering Kyushu University
• 著者所属: Graduate School of Information Science and Electrical Engineering Kyushu University
• 著者所属: Graduate School of Information Science and Electrical Engineering Kyushu University
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science and Electrical Engineering, Kyushu University
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science and Electrical Engineering, Kyushu University
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science and Electrical Engineering, Kyushu University
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science and Electrical Engineering, Kyushu University
• 著者名: Yuta, Harada; Hirotaka, Ono; Kunihiko, Sadakane; Masafumi, Yamashita
• 著者名(英): Yuta, Harada; Hirotaka, Ono; Kunihiko, Sadakane; Masafumi, Yamashita
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: The matching of a bipartite graph is a structure that can be seen in various assignment problems and has long been studied. The semi-matching is an extension of the matching for a bipartite graph G = (U ∪ V E). It is defined as a set of edges M ⊆ E such that each vertex in U is an endpoint of exactly one edge in M. The load-balancing problem is the problem of finding a semi-matching such that the degrees of each vertex in V are balanced. This problem is studied in the context of the task scheduling to find a “balanced” assignment of tasks for machines and an O(|E||U|) time algorithm is proposed. On the other hand in some practical problems only balanced assignments are not sufficient e.g. the assignment of wireless stations (users) to access points (APs) in wireless networks. In wireless networks the quality of the transmission depends on the distance between a user and its AP; shorter distances are more desirable. In this paper We formulate the min-weight load-balancing problem of finding a balanced semi-matching that minimizes the total weight for weighted bipartite graphs. We then give an optimal condition of weighted semi-matchings and propose an O(|E||U||V |) time algorithm.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: The matching of a bipartite graph is a structure that can be seen in various assignment problems and has long been studied. The semi-matching is an extension of the matching for a bipartite graph G = (U ∪ V,E). It is defined as a set of edges, M ⊆ E, such that each vertex in U is an endpoint of exactly one edge in M. The load-balancing problem is the problem of finding a semi-matching such that the degrees of each vertex in V are balanced. This problem is studied in the context of the task scheduling to find a “balanced” assignment of tasks for machines, and an O(|E||U|) time algorithm is proposed. On the other hand, in some practical problems, only balanced assignments are not sufficient, e.g., the assignment of wireless stations (users) to access points (APs) in wireless networks. In wireless networks, the quality of the transmission depends on the distance between a user and its AP; shorter distances are more desirable. In this paper, We formulate the min-weight load-balancing problem of finding a balanced semi-matching that minimizes the total weight for weighted bipartite graphs. We then give an optimal condition of weighted semi-matchings and propose an O(|E||U||V |) time algorithm.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN00116647
• 書誌情報: 情報処理学会論文誌; 巻 48, 号 10, p. 3331-3340, 発行日 2007-10-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7764