Approximability of a {0,1}-matrix Problem

Ljiljana Brankovic; Henning Fernau

Approximability of a {0,1}-matrix Problem

Ljiljana Brankovic
, Henning Fernau

Computer Science

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

Abstract

Weconsider the following combinatorial problem: given an n x m {0,1}-matrix M, find a minimum cardinality set S of mergings between neighboring rows or columns that yields an all-zeros matrix. Here, merging means performing a component-wise AND operation. We prove that this NP-hard minimization problem is factor-2-approximable by relating it to the VERTEX COVER problem on bipartite graphs.

Original language	English
Title of host publication	Proceedings of the Sixteenth Australasian Workshop on Combinatorial Algorithms (AWOCA 2005)
Editors	Joe Ryan, Prabhu Manyem, Kiki Sugeng, Mirka Miller
Place of Publication	Ballarat, Australia
Publisher	University of Ballarat
Pages	39-45
ISBN (Print)	0646452525
Publication status	Published - 30 Sept 2005
Event	AWOCA 2005: Sixteenth Australasian Workshop on Combinatorial Algorithms - University of Ballarat, Ballarat, Australia Duration: 18 Sept 2005 → 21 Sept 2005

Conference

Conference	AWOCA 2005: Sixteenth Australasian Workshop on Combinatorial Algorithms
City	Ballarat, Australia
Period	18/09/05 → 21/09/05

Access to Document

https://hdl.handle.net/1959.11/63391

Handle.net

Persistent link

Cite this

@inproceedings{9905ff0e1f28444fbab085424612489e,

title = "Approximability of a \{0,1\}-matrix Problem",

abstract = "Weconsider the following combinatorial problem: given an n x m \{0,1\}-matrix M, find a minimum cardinality set S of mergings between neighboring rows or columns that yields an all-zeros matrix. Here, merging means performing a component-wise AND operation. We prove that this NP-hard minimization problem is factor-2-approximable by relating it to the VERTEX COVER problem on bipartite graphs.",

author = "Ljiljana Brankovic and Henning Fernau",

year = "2005",

month = sep,

day = "30",

language = "English",

isbn = "0646452525",

pages = "39--45",

editor = "Joe Ryan and Prabhu Manyem and Kiki Sugeng and Mirka Miller",

booktitle = "Proceedings of the Sixteenth Australasian Workshop on Combinatorial Algorithms (AWOCA 2005)",

publisher = "University of Ballarat",

note = "AWOCA 2005: Sixteenth Australasian Workshop on Combinatorial Algorithms ; Conference date: 18-09-2005 Through 21-09-2005",

}

Brankovic, L & Fernau, H 2005, Approximability of a {0,1}-matrix Problem. in J Ryan, P Manyem, K Sugeng & M Miller (eds), Proceedings of the Sixteenth Australasian Workshop on Combinatorial Algorithms (AWOCA 2005). University of Ballarat, Ballarat, Australia, pp. 39-45, AWOCA 2005: Sixteenth Australasian Workshop on Combinatorial Algorithms, Ballarat, Australia, 18/09/05. <https://hdl.handle.net/1959.11/63391>

Approximability of a {0,1}-matrix Problem. / Brankovic, Ljiljana; Fernau, Henning.
Proceedings of the Sixteenth Australasian Workshop on Combinatorial Algorithms (AWOCA 2005). ed. / Joe Ryan; Prabhu Manyem; Kiki Sugeng; Mirka Miller. Ballarat, Australia: University of Ballarat, 2005. p. 39-45.

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

TY - GEN

T1 - Approximability of a {0,1}-matrix Problem

AU - Brankovic, Ljiljana

AU - Fernau, Henning

PY - 2005/9/30

Y1 - 2005/9/30

N2 - Weconsider the following combinatorial problem: given an n x m {0,1}-matrix M, find a minimum cardinality set S of mergings between neighboring rows or columns that yields an all-zeros matrix. Here, merging means performing a component-wise AND operation. We prove that this NP-hard minimization problem is factor-2-approximable by relating it to the VERTEX COVER problem on bipartite graphs.

AB - Weconsider the following combinatorial problem: given an n x m {0,1}-matrix M, find a minimum cardinality set S of mergings between neighboring rows or columns that yields an all-zeros matrix. Here, merging means performing a component-wise AND operation. We prove that this NP-hard minimization problem is factor-2-approximable by relating it to the VERTEX COVER problem on bipartite graphs.

M3 - Conference contribution

SN - 0646452525

SP - 39

EP - 45

BT - Proceedings of the Sixteenth Australasian Workshop on Combinatorial Algorithms (AWOCA 2005)

A2 - Ryan, Joe

A2 - Manyem, Prabhu

A2 - Sugeng, Kiki

A2 - Miller, Mirka

PB - University of Ballarat

CY - Ballarat, Australia

T2 - AWOCA 2005: Sixteenth Australasian Workshop on Combinatorial Algorithms

Y2 - 18 September 2005 through 21 September 2005

ER -

Approximability of a {0,1}-matrix Problem

Abstract

Conference

Access to Document

Handle.net

Fingerprint

Cite this