An Integer Programming-based Local Search for Large-scale Maximal Covering Problems
Journal Title: International Journal on Computer Science and Engineering - Year 2011, Vol 3, Issue 2
Abstract
Maximal covering problem (MCP) is classified as a linear integer optimization problem which can be effectively solved by integer programming technique. However, as the problem size grows, integer programming requires excessive time to get an optimal solution. This paper suggests a method for applying integer programming-based local search (IPbLS) to solve large-scale maximal covering problems. IPbLS, which is a hybrid technique combining integer programming and local search, is a kind of local search using integer programming for neighbor generation. IPbLS itself is very effective for MCP. In addition, we improve the performance of IPbLS for MCP through problem reduction based on the current solution. Experimental results show that the proposed method considerably outperforms any other local search techniques and integer programming.
Authors and Affiliations
Junha Hwang , Sungyoung Kim
Keywords
Related Articles
- EP ID EP155335
- DOI -
- Views 116
- Downloads 0
AN EFFICIENT APPROACH FOR EXTRACTION OF LINEAR FEATURES FROM HIGH RESOLUTION INDIAN SATELLITE IMAGERIES
This paper presents an Object oriented feature extraction pproach in order to classify the linear features like drainage, roads etc. from high resolution Indian satellite imageries. It starts with the multiresolution se...
Reclaiming Individuality of Mysterious Passage
Authorship attribution, the science of inferring characteristics of author from characteristics of documents written by that author become an urgent need to find the original author of anonymous text. In this paper, a no...
Design and Development of Wireless Sensor Network System to Monitor Parameters Influencing Freshwater Fishes
In this paper we have designed, developed and proposed a prototype Wireless Sensor Network (WSN) System to monitor the Fish Farm. Salinity of the fresh water is a prominent parameter and is responsible for the difference...
Multiframe Image Super-resolution – A Comparison
The subject of resolution enhancement has become one of the most important digital processing applications in recent years. This paper focuses on comparison of two multiframe image super-resolution algorithms. Variety of...
Mining Recurrent Pattern Identification on Large Database
Recurrent pattern mining is an important problem in the context of data mining. In this paper data mining algorithms have been discussed and compared. Recurrent pattern mining has been an important area in data mining re...