Title of article
Near-optimalsolutionsforthegeneralizedmax-controlledsetproblem$
Author/Authors
Ivairton M.Santos ، نويسنده , , CarlosA.Martinhon، نويسنده , , LuizS.Ochi ، نويسنده ,
Issue Information
ماهنامه با شماره پیاپی سال 2010
Pages
9
From page
1805
To page
1813
Abstract
In thisworkwedealwithsandwichgraphs G=(V,E) andpresentthenotionofvertices f-controlledbya
subset MDV. Weintroducethegeneralizedmax-controlledsetproblem(GMCSP),whereminimum
gaps(definedbyfunction f) andpositiveweightsareassociatedtoeachvertexof V. Inthiscase,the
objectiveistofindasandwichgraph G in ordertomaximizethesumoftheweightsassociatedtoall
vertices f-controlledby M. Wepresenta 12
approximationalgorithmfortheGMCSPandanew
procedureforfindingfeasiblesolutionsbasedonalinearrelaxation.Thesesolutionsarethenusedas
startingpointinalocalsearchprocedure(TabuSearchwithPathRelinking)lookingforsolutionsof
betterquality.Finally,wepresentsomecomputationalresultsandcompareourheuristicswiththe
optimumsolutionvalueobtainedforsomeinstancesoftheproblem.
Keywords
Sandwich graph problems , Approximation algorithms , Heuristic , Tabu search , Linear programming
Journal title
Computers and Operations Research
Serial Year
2010
Journal title
Computers and Operations Research
Record number
927786
Link To Document