Traffic control with a fixed budget

negative edge weights and an unknown flow circulating on its edges. We
can learn the flow on an edge (and its direction) either by measuring
it directly or by deducing it from the flow conservation property. For a
parameter k ≥ 1, the Flow k-Edge Monitor Problem (k-FEM) is to find
a set of k edges maximizing the total weight of all edges with known
flow. d-Greedy chooses in every iteration d monitor edges maximizing
the weight of edges whose flow becomes known. On unweighted graphs,
we show that the approximation ratio is at most d(3k-2)/(2d-1)k
matching the lower bound for the approximation ratio of d-Greedy which
holds if d2^(d/2) ≤ k.
On weighted graphs, the same bounds are valid if the shortest cycle in
the graph has length at least d. We also study the parameterized
complexity of k-FEM. We show that the problem is W[1]-hard when we
choose as parameter the number of edges whose flow can be computed
from the monitored edges.