[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Help-glpk] The "good enough" set covering problem
From: |
Andrew Makhorin |
Subject: |
Re: [Help-glpk] The "good enough" set covering problem |
Date: |
Mon, 9 Feb 2009 23:17:56 +0300 |
> Got it.
> What influences the runtime - the number of sets, or the size of the
> domain?
The number of binary variables and the structure of subsets to be
included in a cover.
> The reason I #39;m asking is that it #39;s pretty easy to break the
> domain up into smaller domains, find good coverages for each of the
> smaller domains, then take a union of all the resulting minimum sets.
> Optimality is not a requirement here, just a "good enough" solution.
If only a suboptimal solution is needed, such decomposition may
significantly reduce the total solution time.