← All problems

Weighted covering conjecture for d-interval hypergraphs

12 years old · traced to

Let HH be a hypergraph of dd-intervals, let τw(H)\tau_w(H) be its weighted covering number, and let νw(H)\nu_w(H) be its weighted matching number. Weighted covering conjecture. One should have

τw(H)≤d2νw(H).\tau_w(H) \le d^2\nu_w(H).

This bound would improve the proved general estimate τw(H)≤2d2νw(H)\tau_w(H)\le 2d^2\nu_w(H) and would follow in the separated case from the weighted fractional covering conjecture. Its validity in the general case remains open.

References
  1. Ron Aharoni, Tomas Kaiser and Shira Zerbib, “Fractional covers and matchings in families of weighted d-intervals”, arXiv:1402.2064 (2014).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.