My Math Forum Advanced Math: Algorithm to Solve an Optimal Set

 Applied Math Applied Math Forum

 February 6th, 2014, 07:38 AM #1 Newbie   Joined: Feb 2014 Posts: 1 Thanks: 0 Advanced Math: Algorithm to Solve an Optimal Set I want to develop a program which analyzes sets. I think the best way I can describe the program is using an example. For those of you familiar with toggle coverage that is the purpose of this application. The goal is to reach 100% coverage. TestA stresses X% of the chip, but % doesn't matter, what matters is which set of pins/portions of the chip is stressed. So let us say TestA stresses setA and TestB stresses setB, so on and so forth for Y number of tests until we reach 100% coverage. Here is the problem, we want to reduce Y to Y' such that Y' is the minimum ammount of tests required. How? Lets say TestA can be eliminated because by running TestB, C, D we obtain the set which TestA would have covered. The question I have is, I want to do research on this area (IEEE articles and so on) but don't know what to search? I am looking for titles, papers, etc. to help me determine an algorithm. If you have 1000 tests, I don't want to say "Can I eliminate testA with B? no? What about B+C? no? What about B+C+D?" In addition to being very slow, it doesn't account for the fact that sure A might be replaced by B+C+D, but A would have significantly helped with removing D+E+F. I'd appreciate help in going in the right direction. Thanks!
February 6th, 2014, 02:25 PM   #2
Member

Joined: Jun 2008

Posts: 45
Thanks: 0

Re: Advanced Math: Algorithm to Solve an Optimal Set

I think your problem is equivalent to minimum set cover problem. Check it out! Unfortunately efficient algorithm to solve this problem is not known, however if the task is not too big it can be solved by simple bruteforce (and using some tricks like pruning to speed up the search).

Quote:
 Originally Posted by forkconfig The question I have is... ...helped with removing D+E+F.
The last indent is a bit unclear to me, though.

 Tags advanced, algorithm, math, optimal, set, solve

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post flyjoe Real Analysis 0 February 12th, 2013 05:17 PM najken Computer Science 3 September 1st, 2012 02:30 PM TheSwede Advanced Statistics 102 September 19th, 2011 01:48 AM peterle1 Algebra 5 November 23rd, 2009 09:17 AM IsenseHelp Algebra 2 January 11th, 2009 04:10 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top