Open Problems
Open Problems
As probably for everyone who is conducting research, there is a couple of questions I once thought about, but have not found a satisfying answer yet. I am really curious about every new idea with which one might be able to tackle those problems!
The Online Feedback Vertex Set can be understood as a graph that is presented iteratively, and every time a cycle appears, you have to delete a vertex such that the graph gets cycle-free again. Even though this is a very natural problem, to the best of my knowledge it has not been studied extensively yet.
I found out that the competitive ratio can be lower bounded by 4 and that there is a 5-competitive algorithm, but there still remains a gap (see "Delaying Decisions and Reservation Costs"). I conjecture the answer to be 4.
You are given a graph and the promise that every edge has weight 1 or 2. You now have to find a travelling salesman tour, but each edge weight gets revealed to be either 1 or 2 when your agent is on a vertex incident to it (as in Graph Exploration). What is the best competitive ratio you can achieve?
Clearly a ratio of 2 is possible by precomputing a tour, which is optimal if every weight is announced to be either x or 2x for different x. On the restricted case with weights 1 or 2 I believe a ratio of 1.5 might be achievable (see "Graph Exploration with Edge Weight Estimates").