# Online set cover variant? Routing of requests

We have a set of $k$ path requests from $src$ to $dst$ that arrive sequentially.

Each request may have multiple paths, but can choose only one of them. For example, in the Figure shown, there are two paths from $s1$ to $s4$ i.e., path1 : $s1-s2-s3-s4$ and path 2: $s1-s5-s6-s4$.

Further, each node on the path has an associated table that records entries. When a path is chosen, an entry may or may not be added to each node on the path. Whether an entry is added or not depends on the nature of the request, but that is not relevant here. Also, the node tables are independent of each other.

Each table has a limit on the number of entries. Suppose each table can hold a maximum of $n$ entries. When a table is full, that node cannot be chosen on any path. The blue boxes in the figure represent the percent full of each table. The node $s3$ is more utilised than the other nodes. If $s3$ becomes full, the path $s1-s2-s3-s4$ cannot be used to route any more requests.

Now, the challenge is to route the maximum number of requests, as they arrive sequentially. Here is what I have so far.

• Heuristic 1: Choose the path with the least total new table entries added. Using this heuristic, however, can lead to non-uniform utilisation of the tables. Suppose that on the $s1-s2-s3-s4$ path, entries are added only at $s3$. And using the other path, entries are added at $s1$, $s5$, and $s6$. Heuristic 1 will choose path 1, but this may lead to faster fill-up of $s3$ and path1 cannot be used to route more requests.

• Heuristic 2: Choose a cost function for each node based on a) cost to add new entry and b) percentage utilisation of table. Then choose the path with least total cost.

Let us define the cost metric as $cost_{node} = cost_{new\;entry} + \frac{|existing\;entries|}{n}$

Using this heuristic, path 2 will be chosen, given the conditions stated above.

Now my question is two fold:

• Given the two heuristics, how would I go about showing the competitive ratio?

Any help in this regard is appreciated.

Edited: For the sake of simplicity, let us consider for each node on a candidate path, a new table entry is added with a probability $p_i$ and not added with probability $1-p_i$.

Note:

• When a request arrives, and we get a set of candidate paths, we can know in $\mathcal{O}(1)$ time for each node in the path, whether it will have an entry added to its table or not. So in $\mathcal{O}(l)$ time we can know the number of new table entries for a path, where $l$ is the length of the path.
• We have global knowledge about the number of entries in a table of each node at every time instant.
• This sounds pretty complicated. Can you simplify/abstract this any further? When a request arrives, do we know in advance which nodes will have entries added and which won't? Can we ignore the "may or may not be added to each node" and assume an entry is always added to each node on the path, to simplify the problem? What do you mean by "total new rules"? What are rules? Do you mean table entries? Do we have global knowledge of how full the tables at all of the nodes are, when choosing among the candidate paths? – D.W. Apr 13 '18 at 15:42
• Edited . For the sake of simplicity, we can consider all $p_i$ same. Does that help? Sorry for the rules/table entries confusion. Indeed I meant table entries. – Niloy Saha Apr 13 '18 at 17:06
• It seems to me that if you want to get any kind of worst-case bound, you will need to consider (only) the maximum utilisation of any node on the path. Separately, it's not clear whether there is a probability distribution over destination vertices, or whether this should also be given "worst-case" treatment. – j_random_hacker Apr 14 '18 at 13:30

I can suggest another plausible heuristic. Given a graph, you can find use bottleneck shortest paths to find the best path from $s$ to $t$, where "best" is measured by the number of slots in the least empty node that's visited along that path. The larger that number, the better (it means there exists a path with plenty of spare capacity). So, one possible heuristic is to choose whichever path reduces this number the least.