My problem description is a little bit long, I'll try to state it clearly.
Assume that we have a 2x2 square, namely R, containing many points, each of which has a positive weight. Let rmax be the 1x1 square that is inside R and covers points with largest total weights. It is easy to show that the ratio |rmax|/|R| >= 1/4, where |r| and |R| are total weights in r and R, respectively.
My problem is slightly different. In addition to points, we now have edges between some pairs of points, and edges also have weights. And every edge can be covered by at least one 1x1 square (i.e. there is always an 1x1 square that can cover this edge). Weight of a 1x1 square now is the sum of weights of points inside it plus sum of weights of edges inside it, i.e. edges with both ending points also in the 1x1 square. Again, call rmax is the 1x1 square with maximum weights (point weights + edge weights). What is the lower bound of the ratio |rmax|/|R| in this case?
I can prove that if there is no constrain on edge weights, i.e. edge weights can be arbitrarily large, there is no lower bound (in other words, the ratio can be arbitrarily small). So I have one condition on edge weights that the weight of an edge can not be larger than sum of weights of its two points. That means that eij <= wi + wj, where eij, wi and wj are weights of edges connecting points i and j, and weights of points i and j, respectively. So, the final question is, in the case we have constrains on edge weights described above, do we have bound of the ratio |rmax|/|R|? If yes, what is it?
Hope that my problem is well described. Any suggestion is welcomed.
Assume that we have a 2x2 square, namely R, containing many points, each of which has a positive weight. Let rmax be the 1x1 square that is inside R and covers points with largest total weights. It is easy to show that the ratio |rmax|/|R| >= 1/4, where |r| and |R| are total weights in r and R, respectively.
My problem is slightly different. In addition to points, we now have edges between some pairs of points, and edges also have weights. And every edge can be covered by at least one 1x1 square (i.e. there is always an 1x1 square that can cover this edge). Weight of a 1x1 square now is the sum of weights of points inside it plus sum of weights of edges inside it, i.e. edges with both ending points also in the 1x1 square. Again, call rmax is the 1x1 square with maximum weights (point weights + edge weights). What is the lower bound of the ratio |rmax|/|R| in this case?
I can prove that if there is no constrain on edge weights, i.e. edge weights can be arbitrarily large, there is no lower bound (in other words, the ratio can be arbitrarily small). So I have one condition on edge weights that the weight of an edge can not be larger than sum of weights of its two points. That means that eij <= wi + wj, where eij, wi and wj are weights of edges connecting points i and j, and weights of points i and j, respectively. So, the final question is, in the case we have constrains on edge weights described above, do we have bound of the ratio |rmax|/|R|? If yes, what is it?
Hope that my problem is well described. Any suggestion is welcomed.