
Applied Math Applied Math Forum 
 LinkBack  Thread Tools  Display Modes 
February 6th, 2014, 08: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, 03: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:
 

Tags 
advanced, algorithm, math, optimal, set, solve 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Translating Algorithm into Math?  flyjoe  Real Analysis  0  February 12th, 2013 06:17 PM 
Math algorithm  najken  Computer Science  3  September 1st, 2012 03:30 PM 
Help !.. need advanced math formula put into excell !  TheSwede  Advanced Statistics  102  September 19th, 2011 02:48 AM 
Advanced Algebra...well advanced for me =p  peterle1  Algebra  5  November 23rd, 2009 10:17 AM 
Solve for 'x' algebraically, extremely difficult (advanced)?  IsenseHelp  Algebra  2  January 11th, 2009 05:10 PM 