Simultaneous matchings

Khaled Elbassioni; Irit Katriel; Martin Kutz; Meena Mahajan

doi:10.1007/11602613_12

Simultaneous matchings

Khaled Elbassioni, Irit Katriel, Martin Kutz, Meena Mahajan

Electrical Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

6 Scopus citations

Abstract

Given a bipartite graph G = (X ∪ D, E ⊆ X × D), an X-perfect matching is a matching in G that covers every node in X. In this paper we study the following generalisation of the X-perfect matching problem, which has applications in constraint programming: Given a bipartite graph as above and a collection F ⊆ 2^X of k subsets of X, find a subset M ⊆ E of the edges such that for each C ∈ F, the edge set M ∩ (C × D) is a C-perfect matching in G (or report that no such set exists). We show that the decision problem is NP-complete and that the corresponding optimisation problem is in APX when k = O(1) and even APX-complete already for k = 2. On the positive side, we show that a 2/(k + 1)-approximation can be found in 2^kpoly(k, |X ∪ D|) time.

Original language	British English
Title of host publication	Algorithms and Computation - 16th International Symposium, ISAAC 2005, Proceedings
Pages	106-115
Number of pages	10
DOIs	https://doi.org/10.1007/11602613_12
State	Published - 2005
Event	16th International Symposium on Algorithms and Computation, ISAAC 2005 - Hainan, China Duration: 19 Dec 2005 → 21 Dec 2005

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	3827 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	16th International Symposium on Algorithms and Computation, ISAAC 2005
Country/Territory	China
City	Hainan
Period	19/12/05 → 21/12/05

Access to Document

10.1007/11602613_12

Cite this

Elbassioni, K., Katriel, I., Kutz, M., & Mahajan, M. (2005). Simultaneous matchings. In Algorithms and Computation - 16th International Symposium, ISAAC 2005, Proceedings (pp. 106-115). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3827 LNCS). https://doi.org/10.1007/11602613_12

@inproceedings{8f66fde936b943a89183c114f555311b,

title = "Simultaneous matchings",

abstract = "Given a bipartite graph G = (X ∪ D, E ⊆ X × D), an X-perfect matching is a matching in G that covers every node in X. In this paper we study the following generalisation of the X-perfect matching problem, which has applications in constraint programming: Given a bipartite graph as above and a collection F ⊆ 2X of k subsets of X, find a subset M ⊆ E of the edges such that for each C ∈ F, the edge set M ∩ (C × D) is a C-perfect matching in G (or report that no such set exists). We show that the decision problem is NP-complete and that the corresponding optimisation problem is in APX when k = O(1) and even APX-complete already for k = 2. On the positive side, we show that a 2/(k + 1)-approximation can be found in 2kpoly(k, |X ∪ D|) time.",

author = "Khaled Elbassioni and Irit Katriel and Martin Kutz and Meena Mahajan",

year = "2005",

doi = "10.1007/11602613_12",

language = "British English",

isbn = "3540309357",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "106--115",

booktitle = "Algorithms and Computation - 16th International Symposium, ISAAC 2005, Proceedings",

note = "16th International Symposium on Algorithms and Computation, ISAAC 2005 ; Conference date: 19-12-2005 Through 21-12-2005",

}

Elbassioni, K, Katriel, I, Kutz, M & Mahajan, M 2005, Simultaneous matchings. in Algorithms and Computation - 16th International Symposium, ISAAC 2005, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 3827 LNCS, pp. 106-115, 16th International Symposium on Algorithms and Computation, ISAAC 2005, Hainan, China, 19/12/05. https://doi.org/10.1007/11602613_12

Simultaneous matchings. / Elbassioni, Khaled; Katriel, Irit; Kutz, Martin et al.
Algorithms and Computation - 16th International Symposium, ISAAC 2005, Proceedings. 2005. p. 106-115 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3827 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Simultaneous matchings

AU - Elbassioni, Khaled

AU - Katriel, Irit

AU - Kutz, Martin

AU - Mahajan, Meena

PY - 2005

Y1 - 2005

N2 - Given a bipartite graph G = (X ∪ D, E ⊆ X × D), an X-perfect matching is a matching in G that covers every node in X. In this paper we study the following generalisation of the X-perfect matching problem, which has applications in constraint programming: Given a bipartite graph as above and a collection F ⊆ 2X of k subsets of X, find a subset M ⊆ E of the edges such that for each C ∈ F, the edge set M ∩ (C × D) is a C-perfect matching in G (or report that no such set exists). We show that the decision problem is NP-complete and that the corresponding optimisation problem is in APX when k = O(1) and even APX-complete already for k = 2. On the positive side, we show that a 2/(k + 1)-approximation can be found in 2kpoly(k, |X ∪ D|) time.

AB - Given a bipartite graph G = (X ∪ D, E ⊆ X × D), an X-perfect matching is a matching in G that covers every node in X. In this paper we study the following generalisation of the X-perfect matching problem, which has applications in constraint programming: Given a bipartite graph as above and a collection F ⊆ 2X of k subsets of X, find a subset M ⊆ E of the edges such that for each C ∈ F, the edge set M ∩ (C × D) is a C-perfect matching in G (or report that no such set exists). We show that the decision problem is NP-complete and that the corresponding optimisation problem is in APX when k = O(1) and even APX-complete already for k = 2. On the positive side, we show that a 2/(k + 1)-approximation can be found in 2kpoly(k, |X ∪ D|) time.

UR - http://www.scopus.com/inward/record.url?scp=33744961219&partnerID=8YFLogxK

U2 - 10.1007/11602613_12

DO - 10.1007/11602613_12

M3 - Conference contribution

AN - SCOPUS:33744961219

SN - 3540309357

SN - 9783540309352

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 106

EP - 115

BT - Algorithms and Computation - 16th International Symposium, ISAAC 2005, Proceedings

T2 - 16th International Symposium on Algorithms and Computation, ISAAC 2005

Y2 - 19 December 2005 through 21 December 2005

ER -

Simultaneous matchings

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this