Tayzwi

Should be reading more and writing less, but well...

Thursday, September 23, 2004

 

set theoretic question

A main set S and a good number of its subsets A1, A2......Am (m subsets) are given (the total number of subsets is exponential; not all of them are given, but a lot of them (m) are given).

There exists a blackbox algorithm that can take the main set S and the given 'm' subsets and return one combination of disjoint subsets (all pair-wise intersections are null), and whose union gives the main set S.

Say the main set is {1, 2, 3, 4, 5, 6, 7, 8, 9} and the 9 subsets given are
{1, 2, 3}{4, 5, 6}{7, 8, 9}
{1, 2, 3, 4, 5} {6, 7, 8, 9}
{1, 2, 3, 4}{5, 6, 7} {8}{9}

Now we see that the black-box algorithm could return the first row of subsets ({1, 2, 3}{4, 5, 6}{7, 8, 9}) as the answer, the second row as the answer, or the third row as the answer. This is because all these three solutions satisfy the constraint: The returned answer should contain a combination so that they are pairwise disjoint and whose union gives the main set S.

Now, the problem is to somehow use this blackbox algorithm to return the combination of size K. From the above example, if K = 3, the first row should be returned, if K = 4, the last row should be returned.

So, the input to the problem is a set S, a few of its subsets, and a constant K. The output should be K of these subsets so that they are all mutually disjoint and whose union gives S. This problem can use the blackbox algorithm that gives any such solution (the black box doesnt have a clue of K). No combinatorial exhaustive searches allowed.

From my algorithms and complexity course.

Comments: Post a Comment

<< Home

Archives

February 2004   July 2004   August 2004   September 2004   October 2004   November 2004   December 2004   January 2005   February 2005   March 2005   April 2005   May 2005   June 2005   July 2005   August 2005   September 2005   October 2005   November 2005   December 2005   January 2006   February 2006   March 2006   April 2006   May 2006   June 2006   July 2006   August 2006   September 2006   October 2006   November 2006   January 2007   April 2007   May 2007   June 2007   November 2007   December 2007   January 2008   March 2008   June 2008   February 2009   June 2009   February 2010   November 2010  

Quick index to blog-posts I like (from my personal website)

This page is powered by Blogger. Isn't yours? Statscounter is generating statistics of this page