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 114
- Downloads 0
Cost Analysis of a Three Layered MIPv6 (TLMIPv6) Mobility Model and HMIPv6
In this paper cost analysis of a three-layer hierarchical model and HMIPv6 is done. The objective of this work is to examine the signaling cost, tunneling cost and packet dropping probability at top level anchor agents o...
Multi-document Summarization for Query Answering E-learning System
The proposed E-learning system aims at providing a multi-document summarization for documents retrieved from Google and providing the user a precise answer for his/her query under the domain of “Operating Systems”. This...
Face Recognition Technique Using PCA, Wavelet and SVM
We present a method of face recognition in which features are extracted by applying Principal component analysis on wavelet subband. Support vector machine and nearest distance methods are used for classification. Result...
Performance Comparison of Common Table Expressions and Cursors
This paper compares the performance of common table expressions and cursors when implemented for complex queries. Cursor enables traversal of records in a database. Cursors can also be called as “Iterators”, as it perfor...
Multivariable H Robust Controller for a Permanent Magnet Synchronous Machine (PMSM)
Analytical modeling of the PMSM often involves many simplifying assumptions. The model thus obtained is a model where the physical phenomena and dynamics are neglected during the identification of the process such that t...