Name
Abstract | ||
|---|---|---|
We consider MIN SET COVERING when the subsets are constrained to have maximum cardinality 3. We propose an exact algorithm whose worst-case complexity is bounded above by O^*(1.3957^m), where m is the number of sets in the instance. This result improves upon the previously known bound of O^*(1.4391^m). |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1016/j.orl.2006.02.004 | Oper. Res. Lett. |
Keywords | Field | DocType |
min 3-set covering problem,min set covering,exact algorithm,improved worst-case complexity,worst-case complexity,maximum cardinality,min set covering in min set covering,we are given a universe u of elements and a collection s of non- empty subsets of u. the aim is to determine a minimum cardinality sub-collection s0 s,worst case complexity,set cover,set covering problem | Set cover problem,Combinatorics,Mathematical optimization,Algorithm complexity,Exact algorithm,Bounded set,Cardinality,Worst-case complexity,Mathematics | Journal |
Volume | Issue | ISSN |
35 | 2 | Operations Research Letters |
Citations | PageRank | References |
1 | 0.37 | 9 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Federico Della Croce | 1 | 399 | 41.60 |
| Bruno Escoffier | 2 | 430 | 37.32 |
| Vangelis Th. Paschos | 3 | 633 | 63.97 |