## Abstract

For ℋ a hypergraph on vertex set V and t: ℋ → R^{+} , set a(t) = max{∑ {t(A):x, y ∈ A ∈ ℋ} :x, y ∈V, x ≠ y} . We give a simple proof, based on an argument of Pippenger and Spencer [19] of the following rather general statement. Theorem 1.5. Fix k and l. Let ℋ be a k-bounded hypergraph and t a fractional matching of ℋ. Let, furthermore, C_{1} , . . . , C_{i} : ℋ → R^{+} , each satisfying ∑_{A∈ℋ} c^{2}_{i}(A)t(A)<o((∑_{A∈ℋ} c_{i}(A)t(A))^{2}). Then there is matching M of ℋ satisfying ∑_{A∈ℋ} c_{i}(A)∼c_{i}(ℋ) for i = 1 , . . . , l, limits taken as α(t)→0. This contains some previously announced results of the author which interpreted the theorem of the title as a statement about the relation between integer and linear programs and extended it in this vein.

Original language | English (US) |
---|---|

Pages (from-to) | 149-157 |

Number of pages | 9 |

Journal | Random Structures and Algorithms |

Volume | 8 |

Issue number | 2 |

DOIs | |

State | Published - Mar 1996 |

## All Science Journal Classification (ASJC) codes

- Software
- Mathematics(all)
- Computer Graphics and Computer-Aided Design
- Applied Mathematics