String Coverage Problem

Hi.

I'd appreciate your help with the following problem:

Given a set, A, of N (N <= 10000) binary strings, each one is at most
100 digits long.

We say the a binary string C captures another string S if C can be
written beneath S such that any 1 digit of C is written below a 1 digit
of S (but not necessarily vice-versa).

For example C=100010001 covers S=100100010101001, as illustrated by:
100100010101001
....100010001...

We define the pop-count of a binary string as the number of nonzero
digits in it.

The goal is to find a set, B, of strings of pop-count 5, such that each
string in A is covered by at least one string in B.

The problem is an minimization problem on the size of B. That is - an
algorithm should try to create the set B with as few strings as it can
(creating B, such that |B|=N is trivial - any string in A is assumed to
have pop-count of at least 5).

Thanks in advance,
bg.

.

Relevant Pages

  • Re: How to convert extra long strings into their equivalent Hex Strings in VBA (Word 2K)
    ... numbers (upto 18 digits max) into its equivalent Hex String ... Public Function ExpressServiceCode(ByVal ServiceTag As String) As String ... 'the number dblTemp in the specified base, ... Dim lngTemp As Long ...
    (microsoft.public.vb.general.discussion)
  • Re: BigNum -- Floating Point
    ... The 'N' is the number of decimal digits. ... The internal representation is really just a string of bits. ... the number of shifts for various multiples of ten: ... The 'exponent' is very closely related to ...
    (comp.programming)
  • Patterns in pi, copyright law, and philosophy
    ... Whether the offset of a string found in pi can be used as a form on ... then calculate how many digits of pi one would need to raise the ... "An infinite series of numbers is not an exhaustive set of numbers. ... finite string of digits occurs within the decimal expansion of pi, ...
    (sci.math)
  • Re: Patterns in pi, copyright law, and philosophy
    ... The digits of pi are widely believed to be "normal", in the sense that every n digit combination of digits is equally likely, and pass all reasonable tests of randomness. ... The mean length of the offset must at least be equal or greater than the length of the string you are looking for. ... Pi has an infinite representation as a decimal. ... finite string of digits occurs within the decimal expansion of pi, ...
    (sci.math)
  • Re: Required Field for 7 Numeric digits only
    ... Function IsNumber(ByVal Value As String) As Boolean ... > works with verifying that it has 7 digits and is a numeric filled> textbox ... > Private Sub TextBox1_KeyPress ... > Dim IsValid As Boolean ...
    (microsoft.public.excel.programming)