1
$\begingroup$

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!

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ Your problem is probably NP-complete, so you're limited to heuristic algorithms. The performance of such heuristics depend on the graphs you run them on, and absent any theory, this is a purely empirical question. $\endgroup$
    – Yuval Filmus
    Mar 24, 2017 at 9:04
  • $\begingroup$ Thanks for your reply Yuval! I shall edit the question as per your request. Regarding your answer, I am by no means, looking for a definite answer, or looking for someone else to solve the problem for me. Though I was hoping for someone more experienced than myself to let me know whether I'm on the right track generally, or whether I've missed something glaringly obvious or trivial, or if I'm completely off course, in order to perhaps save some time. If I understood your reply, you're saying what I described could work, but needs further testing? So I'm generally in the right direction? $\endgroup$
    – Idra
    Mar 24, 2017 at 9:45
  • 1
    $\begingroup$ Unfortunately I'm not an expert on heuristic algorithms, so I can't help any further. $\endgroup$
    – Yuval Filmus
    Mar 24, 2017 at 9:54

1 Answer 1

Reset to default
2
$\begingroup$

Great project! There are many possibilities. I suggest reviewing the approaches listed in Dealing with intractability: NP-complete problems and trying as many of them as possible to see which tends to work best on the kinds of graphs you have to handle in your class. It will be a fun learning experience, where you get to learn about multiple techniques and get some experience with them.

At minimum, I'd recommend trying some form of local search, such as hill climbing and/or simulated annealing. I have rarely seen situations where genetic algorithms outperform other forms of local search. I'd also recommend trying integer linear programming (ILP) or possibly MaxSAT.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.