A heuristic algorithm for the set k-cover problem

Salehipour, A

A heuristic algorithm for the set k-cover problem

Salehipour, A

Permalink

Publisher:: Springer International Publishing
Publication Type:: Conference Proceeding
Citation:: Communications in Computer and Information Science, 2020, 1173 CCIS, pp. 98-112
Issue Date:: 2020-01-01

Closed Access

	Filename	Description	Size
	Salehipour2020_Chapter_AHeuristicAlgorithmForTheSetK-.pdf	Published Version	508.27 kB	Adobe PDF	View/Open

Copyright Clearance Process

Recently Added
In Progress
Closed Access

This item is closed access and not available.

Full metadata record

Field	Value	Language
dc.contributor.author	Salehipour, A
dc.date.accessioned	2021-04-08T06:35:40Z
dc.date.available	2021-04-08T06:35:40Z
dc.date.issued	2020-01-01
dc.identifier.citation	Communications in Computer and Information Science, 2020, 1173 CCIS, pp. 98-112
dc.identifier.isbn	9783030419127
dc.identifier.issn	1865-0929
dc.identifier.issn	1865-0937
dc.identifier.uri	http://hdl.handle.net/10453/147902
dc.description.abstract	The set k-cover problem (SkCP) is an extension of the classical set cover problem (SCP), in which each row needs to be covered by at least k columns while the coverage cost is minimized. The case of k = 1 refers to the classical SCP. SkCP has many applications including in computational biology. We develop a simple and effective heuristic for both weighted and unweighted SkCP. In the weighted SkCP, there is a cost associated with a column and in the unweighted variant, all columns have the identical cost. The proposed heuristic first generates a lower bound and then builds a feasible solution from the lower bound. We improve the feasible solution through several procedures including a removal local search. We consider three different values for k and test the heuristic on 45 benchmark instances of SCP from OR library. Therefore, we solve 135 instances. Over the solved instances, we show that our proposed heuristic obtains quality solutions.
dc.language	en
dc.publisher	Springer International Publishing
dc.relation	http://purl.org/au-research/grants/arc/DE170100234
dc.relation.ispartof	Communications in Computer and Information Science
dc.relation.isbasedon	10.1007/978-3-030-41913-4_9
dc.rights	info:eu-repo/semantics/closedAccess
dc.title	A heuristic algorithm for the set k-cover problem
dc.type	Conference Proceeding
utslib.citation.volume	1173 CCIS
utslib.for	0802 Computation Theory and Mathematics
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/Faculty of Design, Architecture and Building
pubs.organisational-group	/University of Technology Sydney/Faculty of Design, Architecture and Building/School of Built Environment
utslib.copyright.status	closed_access	*
dc.date.updated	2021-04-08T06:35:38Z
pubs.publication-status	Published
pubs.volume	1173 CCIS

Abstract:

The set k-cover problem (SkCP) is an extension of the classical set cover problem (SCP), in which each row needs to be covered by at least k columns while the coverage cost is minimized. The case of k = 1 refers to the classical SCP. SkCP has many applications including in computational biology. We develop a simple and effective heuristic for both weighted and unweighted SkCP. In the weighted SkCP, there is a cost associated with a column and in the unweighted variant, all columns have the identical cost. The proposed heuristic first generates a lower bound and then builds a feasible solution from the lower bound. We improve the feasible solution through several procedures including a removal local search. We consider three different values for k and test the heuristic on 45 benchmark instances of SCP from OR library. Therefore, we solve 135 instances. Over the solved instances, we show that our proposed heuristic obtains quality solutions.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/147902