I want to solve the following problem (This is a homework problem. Not looking for definite or complete answers):
Maximum One Third Cut:
- Input: An undirected graph G=(V,E) where V={1,2,...,n}, such that |V| is divisible by 3, and a positive integral weight function w:E to N (on edges).
- Goal: Fin a subset of vertices U subset of V such that |U|=|V|/3.
- Objective: Maximize the total weight of the edges between U and its complement.
Of course, you can do that using a full search of all the possiblities. I want a more efficient algorithm though.
I'm thinking about some sort of Local Search algorithm, like Steepest Ascent Hill Climbing (SAHC), or a variation thereof (Simulated Annealing, Random Restart etc.).
- States:
Could be a binary vector, where the i-th element represents whether the vertex i is in U or not (0: not in U, 1: in U), where the number 1-s is |V|/3. - Successors:
Turn one bit off, turn another on. - Heuristic Function:
Sum of all weights of edges between U and V\U. Could be computed when generating a successor, you only need to check the vertex removed and added. Perhaps states can contain a list of edges that are relevant. - Other Parameters:
Like Temprature or amount of restarts allowed could be set by testing the algorithm on graphs of varying in size, weight function and edges, and choosing the best values.
I was also thinking about Evolutionary Search.
Am I on the right track here? Are there better options perhaps?
Any suggestions would be much appreciated.
Thanks!