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
Statistical Approach to Transliteration from English to Punjabi
Machine transliteration plays an important role in natural language applications such as information retrieval and machine translation, especially for handling proper nouns and technical terms. Transliteration is a cruci...
Digital Eye Strain Reduction Techniques: A Review
Digital eye strain or computer vision syndrome (CVS) is caused when we spend considerable amount of time in staring at digital screens of desktop computer, laptop, e-readers, tablets and mobile phones. This paper discuss...
Improvised Interpolation of Contour Lines Using Spider Weaving Approach
Geographically contours are virtual lines drawn across the terrain to join points that are at same elevation from certain reference point. Contours are essential morphological features that are used along with the associ...
On high order methods for solution of nonlinear equation
The objective of this paper is two folds, first to derive a new series of third order methods for solving non-linear equation f(x)=0 involving third, fourth and fifth derivatives of f and secondly to compare the existing...
A Survey : Code Optimization using Refactoring
This position paper identifies emerging trends in refactoring research particulary Refactoring, and enumerates a list of open questions, from practical as well as a theoretical point of view. We suggest these directions...