Automatically assigned DDC number: 004015114

Manually assigned DDC number: 5115

Number of references: 8

Title: Heuristics for the MinLA Problem: Some Theoretical and Empirical Considerations

Author:

Author:

Subject: Jordi Petit I Silvestre,Paul Spirakis Heuristics for the MinLA Problem: Some Theoretical and Empirical Considerations

Description: This paper deals with some aspects on finding good solutions for the Minimum Linear Arrangement problem (MinLA). We consider some random type of sparse graphs, for which it is possible to obtain trivial constant approximations. For similar graphs, we prove that Metropolis can find good solutions, whereas we exhibit an instance for which Hill Climbing is expected to need an exponential number of steps to hit an optimum. Motivated by the last results, we present an heuristic (SS+SA) to approximate the MinLA problem on sparse graphs. The heuristic consists in using Spectral Sequencing to obtain a first primal solution and after improving it locally through (Parallel) Simulated Annealing. In the last part of the paper, we report experimental results obtained with the SS+SA heuristic when applied to a set of large sparse geometric graphs. Compared to other heuristics, the measurements obtained on an IBM SP2 computer with 8 processors show that the new heuristic improves the solution qualit...

Contributor: The Pennsylvania State University CiteSeer Archives

Publisher: unknown

Date: 1998-03-26

Pubyear: 1998

Format: ps

Identifier: http://citeseer.ist.psu.edu/175076.html

Source: http://www.lsi.upc.es/dept/techreps/ps/R98-15.ps.gz

Language: en

Relation:

Relation:

Relation:

Relation:

Relation:

Relation:

Relation:

Relation:

Rights: unrestricted

Graph

<?xml   version="1.0"   encoding="UTF-8"?>

<references_metadata>

      <rec   ID="/24280.html"   Type="misc"   CiteSeer_Book=""   CiteSeer_Volume=""   Title="A   compendium   of   NP   optimization   problems,">

            <identifier   Org="ISBN:0471419028"   Paper_ID="/24280.html"   Extracted="0471419028"   DDC="621.382"   Normalized_DDC="621382"   Normalized_Weight="0.05263157894736842"   />

            <identifier   Org="ISBN:052188473X"   Paper_ID="/24280.html"   Extracted="052188473X"   DDC="511.3/52"   Normalized_DDC="511352"   Normalized_Weight="0.05263157894736842"   />

            <identifier   Org="ISBN:0792352939"   Paper_ID="/24280.html"   Extracted="0792352939"   DDC="519.7/6"   Normalized_DDC="51976"   Normalized_Weight="0.05263157894736842"   />

            <identifier   Org="ISBN:0849326494"   Paper_ID="/24280.html"   Extracted="0849326494"   DDC="511.3"   Normalized_DDC="5113"   Normalized_Weight="0.05263157894736842"   />

            <identifier   Org="ISBN:1584885505"   Paper_ID="/24280.html"   Extracted="1584885505"   DDC="005.1"   Normalized_DDC="0051"   Normalized_Weight="0.05263157894736842"   />

            <identifier   Org="ISBN:3540261990"   Paper_ID="/24280.html"   Extracted="3540261990"   DDC="519.77"   Normalized_DDC="51977"   Normalized_Weight="0.05263157894736842"   />

            <identifier   Org="ISBN:3540419209"   Paper_ID="/24280.html"   Extracted="3540419209"   DDC="006.3"   Normalized_DDC="0063"   Normalized_Weight="0.05263157894736842"   />

            <identifier   Org="ISBN:3540421440"   Paper_ID="/24280.html"   Extracted="3540421440"   DDC="006.3"   Normalized_DDC="0063"   Normalized_Weight="0.05263157894736842"   />

            <identifier   Org="ISBN:3540424237"   Paper_ID="/24280.html"   Extracted="3540424237"   DDC="005.1"   Normalized_DDC="0051"   Normalized_Weight="0.05263157894736842"   />

            <identifier   Org="ISBN:3540438661"   Paper_ID="/24280.html"   Extracted="3540438661"   DDC="511.8"   Normalized_DDC="5118"   Normalized_Weight="0.05263157894736842"   />

            <identifier   Org="ISBN:3540600175"   Paper_ID="/24280.html"   Extracted="3540600175"   DDC="004/.01/5113"   Normalized_DDC="004015113"   Normalized_Weight="0.05263157894736842"   />

            <identifier   Org="ISBN:3540602461"   Paper_ID="/24280.html"   Extracted="3540602461"   />

            <identifier   Org="ISBN:3540606157"   Paper_ID="/24280.html"   Extracted="3540606157"   DDC="005.1/4/015113"   Normalized_DDC="00514015113"   Normalized_Weight="0.05263157894736842"   />

            <identifier   Org="ISBN:354061043X"   Paper_ID="/24280.html"   Extracted="354061043X"   DDC="519.3"   Normalized_DDC="5193"   Normalized_Weight="0.05263157894736842"   />

            <identifier   Org="ISBN:3540613323"   Paper_ID="/24280.html"   Extracted="3540613323"   DDC="004"   Normalized_DDC="004"   Normalized_Weight="0.05263157894736842"   />

            <identifier   Org="ISBN:3540625925"   Paper_ID="/24280.html"   Extracted="3540625925"   DDC="511.3"   Normalized_DDC="5113"   Normalized_Weight="0.05263157894736842"   />

            <identifier   Org="ISBN:3540631720"   Paper_ID="/24280.html"   Extracted="3540631720"   DDC="004/.01/5113"   Normalized_DDC="004015113"   Normalized_Weight="0.05263157894736842"   />

            <identifier   Org="ISBN:3540632484"   Paper_ID="/24280.html"   Extracted="3540632484"   DDC="004/.01/5114"   Normalized_DDC="004015114"   Normalized_Weight="0.05263157894736842"   />

            <identifier   Org="ISBN:3540647368"   Paper_ID="/24280.html"   Extracted="3540647368"   DDC="005.1"   Normalized_DDC="0051"   Normalized_Weight="0.05263157894736842"   />

            <identifier   Org="ISBN:3540678239"   Paper_ID="/24280.html"   Extracted="3540678239"   DDC="004"   Normalized_DDC="004"   Normalized_Weight="0.05263157894736842"   />

      </rec>

      <rec   ID="/63494.html"   Type="misc"   CiteSeer_Book=""   CiteSeer_Volume=""   Title="Parallel   Algorithms   for   the   Minimum   Cut   and   the   Minimum   Length   Tree   Layout   Problems,"   />

      <rec   ID="/10287.html"   Type="inproceedings"   CiteSeer_Book="SPDP   4th   IEEE   Symposium   on   Parallel   and   Distributed   Processing"   CiteSeer_Volume=""   Title="A   General   Purpose   Distributed   Implementation   of   Simulated   Annealing,">

            <identifier   Org="ISBN:0769501435"   Paper_ID="/10287.html"   Extracted="0769501435"   />

            <identifier   Org="ISBN:0818624205"   Paper_ID="/10287.html"   Extracted="0818624205"   />

            <identifier   Org="ISBN:0818632003"   Paper_ID="/10287.html"   Extracted="0818632003"   />

            <identifier   Org="ISBN:2710808757"   Paper_ID="/10287.html"   Extracted="2710808757"   />

      </rec>

      <rec   ID="/92730.html"   Type="inproceedings"   CiteSeer_Book="IEEE   Symposium   on   Foundations   of   Computer   Science"   CiteSeer_Volume=""   Title="Divide-and-Conquer   Approximation   Algorithms   via   Spreading   Metrics   (Extended   Abstract),">

            <identifier   Org="ISBN:0780331214"   Paper_ID="/92730.html"   Extracted="0780331214"   />

            <identifier   Org="ISBN:1402063288"   Paper_ID="/92730.html"   Extracted="1402063288"   DDC="004.16"   Normalized_DDC="00416"   Normalized_Weight="0.5"   />

            <identifier   Org="ISBN:1581130678"   Paper_ID="/92730.html"   Extracted="1581130678"   />

            <identifier   Org="ISBN:1581136749"   Paper_ID="/92730.html"   Extracted="1581136749"   />

            <identifier   Org="ISBN:1584886781"   Paper_ID="/92730.html"   Extracted="1584886781"   DDC="004/.33"   Normalized_DDC="00433"   Normalized_Weight="0.5"   />

      </rec>

      <rec   ID="/184851.html"   Type="misc"   CiteSeer_Book=""   CiteSeer_Volume=""   Title="The   markov   chain   monte   carlo   method:   an   approach   to   approximate   counting   and   integration,">

            <identifier   Org="ISBN:0262195682"   Paper_ID="/184851.html"   Extracted="0262195682"   DDC="006.3"   Normalized_DDC="0063"   Normalized_Weight="0.058823529411764705"   />

            <identifier   Org="ISBN:0470772697"   Paper_ID="/184851.html"   Extracted="0470772697"   DDC="519.2"   Normalized_DDC="5192"   Normalized_Weight="0.058823529411764705"   />

            <identifier   Org="ISBN:0521653762"   Paper_ID="/184851.html"   Extracted="0521653762"   DDC="511/.6"   Normalized_DDC="5116"   Normalized_Weight="0.058823529411764705"   />

            <identifier   Org="ISBN:0792378091"   Paper_ID="/184851.html"   Extracted="0792378091"   DDC="004"   Normalized_DDC="004"   Normalized_Weight="0.058823529411764705"   />

            <identifier   Org="ISBN:0821808273"   Paper_ID="/184851.html"   Extracted="0821808273"   DDC="519.2"   Normalized_DDC="5192"   Normalized_Weight="0.058823529411764705"   />

            <identifier   Org="ISBN:0821809636"   Paper_ID="/184851.html"   Extracted="0821809636"   DDC="511/.5"   Normalized_DDC="5115"   Normalized_Weight="0.058823529411764705"   />

            <identifier   Org="ISBN:0898714109"   Paper_ID="/184851.html"   Extracted="0898714109"   />

            <identifier   Org="ISBN:1402072953"   Paper_ID="/184851.html"   Extracted="1402072953"   DDC="004/.01/51"   Normalized_DDC="0040151"   Normalized_Weight="0.058823529411764705"   />

            <identifier   Org="ISBN:1584885505"   Paper_ID="/184851.html"   Extracted="1584885505"   DDC="005.1"   Normalized_DDC="0051"   Normalized_Weight="0.058823529411764705"   />

            <identifier   Org="ISBN:186094700X"   Paper_ID="/184851.html"   Extracted="186094700X"   DDC="572.80285"   Normalized_DDC="57280285"   Normalized_Weight="0.058823529411764705"   />

            <identifier   Org="ISBN:3110168103"   Paper_ID="/184851.html"   Extracted="3110168103"   DDC="511.3"   Normalized_DDC="5113"   Normalized_Weight="0.058823529411764705"   />

            <identifier   Org="ISBN:3540275800"   Paper_ID="/184851.html"   Extracted="3540275800"   DDC="005.1"   Normalized_DDC="0051"   Normalized_Weight="0.058823529411764705"   />

            <identifier   Org="ISBN:3540423435"   Paper_ID="/184851.html"   Extracted="3540423435"   DDC="006.3/1"   Normalized_DDC="00631"   Normalized_Weight="0.058823529411764705"   />

            <identifier   Org="ISBN:3540424709"   Paper_ID="/184851.html"   Extracted="3540424709"   DDC="004/.01/5114"   Normalized_DDC="004015114"   Normalized_Weight="0.058823529411764705"   />

            <identifier   Org="ISBN:3540667229"   Paper_ID="/184851.html"   Extracted="3540667229"   DDC="006.3/7"   Normalized_DDC="00637"   Normalized_Weight="0.058823529411764705"   />

            <identifier   Org="ISBN:3540679960"   Paper_ID="/184851.html"   Extracted="3540679960"   DDC="004/.01/5114"   Normalized_DDC="004015114"   Normalized_Weight="0.058823529411764705"   />

            <identifier   Org="ISBN:3764371285"   Paper_ID="/184851.html"   Extracted="3764371285"   DDC="511/.6"   Normalized_DDC="5116"   Normalized_Weight="0.058823529411764705"   />

            <identifier   Org="ISBN:9812565175"   Paper_ID="/184851.html"   Extracted="9812565175"   DDC="332.6"   Normalized_DDC="3326"   Normalized_Weight="0.058823529411764705"   />

      </rec>

      <rec   ID="/306220.html"   Type="inproceedings"   CiteSeer_Book="IEEE   Symposium   on   Foundations   of   Computer   Science"   CiteSeer_Volume=""   Title="Simulated   Annealing   for   Graph   Bisection,">

            <identifier   Org="ISBN:0546693792"   Paper_ID="/306220.html"   Extracted="0546693792"   />

            <identifier   Org="ISBN:0818643706"   Paper_ID="/306220.html"   Extracted="0818643706"   DDC="004"   Normalized_DDC="004"   Normalized_Weight="0.1111111111111111"   />

            <identifier   Org="ISBN:0818665823"   Paper_ID="/306220.html"   Extracted="0818665823"   />

            <identifier   Org="ISBN:0818685913"   Paper_ID="/306220.html"   Extracted="0818685913"   />

            <identifier   Org="ISBN:0898713552"   Paper_ID="/306220.html"   Extracted="0898713552"   DDC="519.4/0285/51"   Normalized_DDC="5194028551"   Normalized_Weight="0.1111111111111111"   />

            <identifier   Org="ISBN:0898714907"   Paper_ID="/306220.html"   Extracted="0898714907"   />

            <identifier   Org="ISBN:158113858X"   Paper_ID="/306220.html"   Extracted="158113858X"   />

            <identifier   Org="ISBN:3540272372"   Paper_ID="/306220.html"   Extracted="3540272372"   DDC="005.1"   Normalized_DDC="0051"   Normalized_Weight="0.1111111111111111"   />

            <identifier   Org="ISBN:3540275800"   Paper_ID="/306220.html"   Extracted="3540275800"   DDC="005.1"   Normalized_DDC="0051"   Normalized_Weight="0.1111111111111111"   />

            <identifier   Org="ISBN:3540424709"   Paper_ID="/306220.html"   Extracted="3540424709"   DDC="004/.01/5114"   Normalized_DDC="004015114"   Normalized_Weight="0.1111111111111111"   />

            <identifier   Org="ISBN:3540438661"   Paper_ID="/306220.html"   Extracted="3540438661"   DDC="511.8"   Normalized_DDC="5118"   Normalized_Weight="0.1111111111111111"   />

            <identifier   Org="ISBN:3540440402"   Paper_ID="/306220.html"   Extracted="3540440402"   DDC="004/.01/51"   Normalized_DDC="0040151"   Normalized_Weight="0.1111111111111111"   />

            <identifier   Org="ISBN:3540646221"   Paper_ID="/306220.html"   Extracted="3540646221"   DDC="511/.6"   Normalized_DDC="5116"   Normalized_Weight="0.1111111111111111"   />

            <identifier   Org="ISBN:3540679014"   Paper_ID="/306220.html"   Extracted="3540679014"   DDC="004.0151"   Normalized_DDC="0040151"   Normalized_Weight="0.1111111111111111"   />

      </rec>

      <rec   ID="/125830.html"   Type="misc"   CiteSeer_Book=""   CiteSeer_Volume=""   Title="Random   Walks   on   Graphs:   A   Survey,">

            <identifier   Org="ISBN:0262195348"   Paper_ID="/125830.html"   Extracted="0262195348"   />

            <identifier   Org="ISBN:0521497973"   Paper_ID="/125830.html"   Extracted="0521497973"   DDC="511/.6"   Normalized_DDC="5116"   Normalized_Weight="0.07692307692307693"   />

            <identifier   Org="ISBN:1581136749"   Paper_ID="/125830.html"   Extracted="1581136749"   />

            <identifier   Org="ISBN:158113858X"   Paper_ID="/125830.html"   Extracted="158113858X"   />

            <identifier   Org="ISBN:3540204369"   Paper_ID="/125830.html"   Extracted="3540204369"   DDC="004.67/8"   Normalized_DDC="004678"   Normalized_Weight="0.07692307692307693"   />

            <identifier   Org="ISBN:3540221727"   Paper_ID="/125830.html"   Extracted="3540221727"   DDC="004.36"   Normalized_DDC="00436"   Normalized_Weight="0.07692307692307693"   />

            <identifier   Org="ISBN:3540235272"   Paper_ID="/125830.html"   Extracted="3540235272"   DDC="006.4"   Normalized_DDC="0064"   Normalized_Weight="0.07692307692307693"   />

            <identifier   Org="ISBN:3540241280"   Paper_ID="/125830.html"   Extracted="3540241280"   DDC="004.35"   Normalized_DDC="00435"   Normalized_Weight="0.07692307692307693"   />

            <identifier   Org="ISBN:3540288694"   Paper_ID="/125830.html"   Extracted="3540288694"   DDC="621.367"   Normalized_DDC="621367"   Normalized_Weight="0.07692307692307693"   />

            <identifier   Org="ISBN:3540289690"   Paper_ID="/125830.html"   Extracted="3540289690"   DDC="006.4/2"   Normalized_DDC="00642"   Normalized_Weight="0.07692307692307693"   />

            <identifier   Org="ISBN:3540294147"   Paper_ID="/125830.html"   Extracted="3540294147"   DDC="004"   Normalized_DDC="004"   Normalized_Weight="0.07692307692307693"   />

            <identifier   Org="ISBN:3540302875"   Paper_ID="/125830.html"   Extracted="3540302875"   DDC="006.3/7"   Normalized_DDC="00637"   Normalized_Weight="0.07692307692307693"   />

            <identifier   Org="ISBN:3540440119"   Paper_ID="/125830.html"   Extracted="3540440119"   DDC="006.4"   Normalized_DDC="0064"   Normalized_Weight="0.07692307692307693"   />

            <identifier   Org="ISBN:3540705740"   Paper_ID="/125830.html"   Extracted="3540705740"   />

            <identifier   Org="ISBN:354072902X"   Paper_ID="/125830.html"   Extracted="354072902X"   DDC="006.4/2"   Normalized_DDC="00642"   Normalized_Weight="0.07692307692307693"   />

            <identifier   Org="ISBN:3540772197"   Paper_ID="/125830.html"   Extracted="3540772197"   />

            <identifier   Org="ISBN:3540852182"   Paper_ID="/125830.html"   Extracted="3540852182"   DDC="511.1"   Normalized_DDC="5111"   Normalized_Weight="0.07692307692307693"   />

            <identifier   Org="ISBN:9810239467"   Paper_ID="/125830.html"   Extracted="9810239467"   DDC="510.92/2"   Normalized_DDC="510922"   Normalized_Weight="0.07692307692307693"   />

      </rec>

      <rec   ID="/427660.html"   Type="misc"   CiteSeer_Book=""   CiteSeer_Volume=""   Title="Approximation   Heuristics   and   Benchmarkings   for   the   MinLA   Problem,">

            <identifier   Org="ISBN:1402010818"   Paper_ID="/427660.html"   Extracted="1402010818"   DDC="621.39/5"   Normalized_DDC="621395"   Normalized_Weight="0.3333333333333333"   />

            <identifier   Org="ISBN:354044310X"   Paper_ID="/427660.html"   Extracted="354044310X"   DDC="511/.5"   Normalized_DDC="5115"   Normalized_Weight="0.3333333333333333"   />

            <identifier   Org="ISBN:3540667318"   Paper_ID="/427660.html"   Extracted="3540667318"   DDC="004.0151"   Normalized_DDC="0040151"   Normalized_Weight="0.3333333333333333"   />

            <identifier   Org="ISBN:9812388559"   Paper_ID="/427660.html"   Extracted="9812388559"   />

      </rec>

      <rec   ID="SELF"   Type="SELF"   CiteSeer_Book="SELF"   CiteSeer_Volume="SELF"   Title="Heuristics   for   the   MinLA   Problem:   Some   Theoretical   and   Empirical   Considerations"   />

</references_metadata>

www.000webhost.com