Optimizing the two-dimensional bandwidth problem under the maximum norm using exact and heuristic approaches

Abstract

Paper under review. To be added upon acceptance.

Authors

• Sergio Cavero Díaz¹

• Eduardo G. Pardo¹ *

• Eduardo Rodriguez-Tello²

• Eric Monfroy³

• Claudia Vasconcellos-Gaete³

Affiliations

1. Departamento de Informática y Estadística, Universidad Rey Juan Carlos — C. Tulipán, s/n, Móstoles, 28933, Madrid, Spain

2. Cinvestav, Unidad Tamaulipas — Km. 5.5 Carretera Victoria - Soto La Marina, Victoria, 87130, Tamaulipas, Mexico

3. LERIA, Université d'Angers — 2 Bd de Lavoisier, Angers, 49000, France

*Corresponding author.

Datasets

Instances are categorized in different datasets inside the instances folder. All instances are either from the https://archive.ics.uci.edu/ml/index.php, the Harwell-Boeing Sparse Matrix Collection, or generated based on graph families described in the paper.

Instance format

Each instance is encoded as a plain text file representing a graph:

• The first line contains the number of vertices n and edges m.
• Each subsequent line contains a pair of integers u v representing an edge between vertex u and vertex v.
• Vertices are indexed from 0 to n-1.

Example:

10 15
0 1
0 2
1 3
...

CBMA

Execution of the program can be done via the command line.

Example 1: execute default experiment with the default set of instances

java -jar target/CBMA.jar 

Example 2: execute using a different set of instances, located inside the newinstances folder.

java -jar target/CBMA.jar --instances.path.default=newinstances

Cite

Consider citing our paper if used in your own work:

DOI

https://doi.org/XXXXXXX

Bibtex

@article{cavero2025heuristic,
  title={Heuristic and Exact Approaches for the Two-Dimensional Bandwidth Problem},
  author={Cavero, Sergio and Pardo, Eduardo G. and Rodriguez-Tello, Eduardo and Monfroy, Eric and Vasconcellos-Gaete, Claudia},
  journal={XXXXXX},
  year={202X},
  doi={XXXXXXX}
}

Powered by MORK (Metaheuristic Optimization framewoRK)

	Mork is a Java framework for easily solving hard optimization problems. You can create a project and try the framework in under one minute. See the documentation or the source code.