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

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...

Download PDF file
  • EP ID EP155335
  • DOI -
  • Views 106
  • Downloads 0

How To Cite

Junha Hwang, Sungyoung Kim (2011). An Integer Programming-based Local Search for Large-scale Maximal Covering Problems. International Journal on Computer Science and Engineering, 3(2), 837-843. https://europub.co.uk/articles/-A-155335