CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 2 of 2
  1. #1
    Join Date
    May 2013
    Posts
    1

    Smile Disjoint pairs problem

    Hi to all,
    excuse me in advance if I have done something wrong in posting this thread (I'm new ).
    My problem is the following:
    I have a set of pairs identified by two end point: u and, that respectively represent two process connected (u sends and v receives), and each process can hold one connection at a time, so I have to divide the computation in communication rounds so that in each round communicate as many process as possibile. This example may explain better the idea:
    I have
    1-2
    1-3
    1-4
    2-1
    2-3
    3-4
    3-5
    4-6
    4-2
    ...
    If I choose 1-2 in a communication round I can't choose in the same communication round 1-3, 1-4, 2-1, 2-3, 4-2 because these pairs involve process 1 or 2.
    I tried to solve the problem with a greedy algorithm that for each pair choose a round that doesn't intersect with it and if there are no feasible rounds it creates a new one.
    I find lots of problems in literature regarding path coloring, arc coloring and interval scheduling, but I'm not sure if I'm dealing with a difficoult problem, I mean NP-hard, or with a polynomial one, so I can't prove if my solution is optimal. Can you help me? Do you think my problem is reconducible to path coloring? If so, are there some approximation algorithms that give less than O(n^2)?
    Thanks in advance to all
    luca v.

  2. #2
    Join Date
    May 2009
    Posts
    2,413

    Re: Disjoint pairs problem

    Quote Originally Posted by lucav View Post
    path coloring, arc coloring and interval scheduling
    To me it looks like a set cover problem,

    http://en.wikipedia.org/wiki/Set_cover_problem

    There it says the optimal approximate strategy is to greedily select the largest set in each stage.

    Translated to this problem it would mean to find the largest set of non-conflicting pairs and send them together in one round. This is then repeated until all pairs have been sent. The collection of largest sets will be mutually disjoint and together cover the total set of all pairs.

    Each pair is associated with a set of non-conflicting other pairs. The task is to find the largest of these associated sets. It's quite easy to calculate how many members there are in such a set. From the total number of pairs, N, it's just to subtract the number of conflicting pairs (those with the same <from> or <to>). The <from> and <to> counts can be held in two look-up tables (one for <from> and one for <to>).

    Setting up the look-up tables and walking through all pairs to select the pair with the largest associated set and then actually generate the largest set from the pair is O(N). The link above indicates this must be repeated log(N) times. That would result in a total complexity of O(N * logN) on average.
    Last edited by nuzzle; May 3rd, 2013 at 03:08 AM.

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  





Click Here to Expand Forum to Full Width

Featured