Anti-Bandwidth Maximization Problem

Problem definition:

Construction of a starting solution for the different heuristic methods:

For the moment, two different approaches have been considered, given an instance of a graph G(V, E) and a solution represented as a permutation of the different vertices in V in a set of size |V|:

• The first, to simply choose the different labels as random integers within the available numbers from 1 to |V|, which is, in itself, efficient, but not enoughly consistent for the methods applied afterwards.

• The second, a greedy algorithm that decides with a breadth first search starting in a first labeled vertex, the labeling for the neighbors of the currently visited vertex, based on the __optimality criteria AB(V_i)__ applied to each neighbor following a first-come-first-served approach. A pseudocode for the described method is provided:

char[] starting solution = {A,  ...}; // A is assigned to the label 1 by default
int[] non-visited = {2, 3, 4, 5...};  // Rest of the labels

for (auto vertex : GRAPH) {
  for (auto neighbor : vertex.neighborhood) {
    if (!neighbor.isLabeled()) {      // If neighbor does not have a label assigned
      int min_label = 0;    // Position in the array
      for (int i = 1; i < non-visited.size(); i++) {
        if (AB_vertex(vertex.label, non-visited[i]) < AB_vertex(vertex.label, non-visited[min_label])) {  
          //min{f[v_i] - f[n_i]}
          min_label = i;
        }
      }

      // label neighbor as min_label
      starting_solution[min_label] = neighbor;
      non_visited.erase(neighbor);     
    }
  }

  if (non-visited.empty()) break;   // optimization
}

*DISCLAIMER: actual implementation may vary the data structures utilized in provided examples.

GRASP RCL criteria

For the GRASP construction algorithm, a simple cardinality criteria can be followed, applying the __AB(v_i) function to the total of label candidates and choosing labeling at random between the first k__ candidates.