Re: To which field does this belong?

On Fri, 22 Sep 2006 07:53:01 -0700, sol.hari wrote:

Which field of mathematics would describe an algorithm to solve the
problem below? What keywords should I use to point me in the right
direction?

Problem:
I have a set of n distinct elements T = {e_1, e_2, ..., e_n}, and m
subsets of T, S_1, S2, ... S_m, that can overlap.
I need to find the minimum number of subsets whose union equals T.

Thanks,
Hari
This is the set cover problem. Search for that in Wikipedia for example.
This is a (np) hard problem.
Duncan


.

Relevant Pages

  • Quantum Gravity 291.99: More Re 1 + y - Dt(y) Generates Quantum Theory and Gravitation
    ... physics under those keywords or similar keywords, ... Thirring Model of Dirac fields and QFT, ... Each of those can be accessed in Wikipedia under its name. ... derivatives does similarly or the Sine-Gordon equation of solitons and ...
    (sci.physics)
  • Re: To which field does this belong?
    ... Arturo Magidin wrote: ... What keywords should I use to point me in the right ... S_m, that can overlap. ... Or possibly as an integer programming optimization problem. ...
    (sci.math)
  • Re: To which field does this belong?
    ... What keywords should I use to point me in the right ... S_m, that can overlap. ... what I accept as reality." ... Arturo Magidin ...
    (sci.math)
  • Re: Horizon 10.1.11 - What is one degree?
    ... Koning) sprachen: ... Do you remember names and/or keywords? ... Try "dual slit experiment" on Wikipedia, it's just a link or two from ...
    (uk.media.tv.misc)
  • Re: To which field does this belong?
    ... What keywords should I use to point me in the right ... S_m, that can overlap. ... I need to find the minimum number of subsets whose union equals T. ... Your problem is a "set covering problem". ...
    (sci.math)