Automatic Locallized Local Search

Topic Description

Subdividing a problem into manageable pieces is a critical task in effectively parallelizing computation and even accelerating sequential computation. A key method that has received a lot of attention for doing so is graph partitioning.  The basic graph partitioning problem is to split a graph's vertex set into a given number of almost equally sized blocks while minimizing a suitable objective function.  The simplest and perhaps most common form of graph partitioning asks for the vertex set to be partitioned into k blocks, while minimizing the number of edges between the blocks (called cut edges). Even this most basic variant is NP-hard, by a reduction from 3SAT. Graph partitioning has many application areas, including VLSI, scientific computing, designing scalable distributed systems, genome sequencing, and routing in road networks. The role that graph partitioning plays in each of these applications, is one of efficiency. Given its usage in many varied areas, it is critical to understand how a high-quality graph partition can be computed and used in practice.

In recent year, experiments have shown that a more locallized approach to local search helps to find much better solutions than competing codes. In this thesis, we want to combine classicial local search algorithms that are NOT localized with an approach to detect independent improvments found by local search.

You should have:

  • solid knowledge in algorithms and data structures
  • good knowledge in C++