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