| The Structure and Number of Global Roundings of a Graph (2008) | |||||||||||||||||
Abstract | |||||||||||||||||
| Given a connected weighted graph G =(V,E), we consider a hypergraph HG = (V,PG) corresponding to the set of all shortest paths in G. For a given real assignment a on V satisfying 0 ≤ a(v) ≤ 1, a global rounding α with respect to HG is a binary assignment satisfying that | � v∈F a(v) − α(v) | < 1 for every F ∈PG. We conjecture that there are at most |V | + 1 global roundings for HG, and also the set of global roundings is an affine independent set. We give several positive evidences for the conjecture. | |||||||||||||||||
Publication details | |||||||||||||||||
| |||||||||||||||||