Article ID: | iaor20051029 |

Country: | Germany |

Volume: | 98 |

Issue: | 1/3 |

Start Page Number: | 355 |

End Page Number: | 368 |

Publication Date: | Jan 2003 |

Journal: | Mathematical Programming |

Authors: | Boros E., Elbassioni K., Gurvich V., Khachiyan L. |

Abstract:

A result of Balas and Yu states that the number of maximal independent sets of a graph ^{p} + 1, where δ is the number of pairs of vertices in ^{log t/c (2Q,β)}}^{c}(ρ^{c/log β} − 1) = 1. This bound is nearly sharp for the Boolean case ℒ = {0, 1}^{n}, and it allows for the efficient generation of all minimal feasible sets to a given system of polymatroid inequalities with quasi-polynomially bounded right-hand sides