1
$\begingroup$

Question:
Given a finite symmetric TSP instance with $2n$ sites, what is the complexity of and what are algorithms for determining two sets of sites $A$ and $B$, each containing $n$ elemenents so that

  • the difference the weight sums of edges in $A$ and of edges in $B$ is minimal

  • the weight sum of edges connecting a site in $A$ with a site in $B$ is minimal?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

Both of these problems share many similarities with the partition problem for which there exists efficient greedy algorithms, dynamic programming approaches, and exact methods (see link).

Improve this answer
$\endgroup$
1
  • $\begingroup$ As the partition problem doesn't have to deal with interdependence between the individual numbers, it apparently provides a lower bound for the complexity of "graph partitioning" problem. I currently don't see how to transform the graph partitioning problem to the "set partitioning" problem to make the existing algorithms directly applicable. $\endgroup$
    – Manfred Weis
    Commented Aug 20, 2018 at 3:16

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .