Editing Open Problems:102
Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.
The edit can be undone.
Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.
| Latest revision | Your text | ||
| Line 3: | Line 3: | ||
|who=Jukka Suomela | |who=Jukka Suomela | ||
}} | }} | ||
| β | In this question, the input is the underlying graph $G=(V,E)$, promised to have maximum degree at most $\Delta$, and the goal is to compute an orientation of the edges of $E$ which makes all edges | + | |
| + | In this question, the input is the underlying graph $G=(V,E)$, promised to have maximum degree at most $\Delta$, and the goal is to compute an orientation of the edges of $E$ which makes all edges "happy." Specifically, for any given orientation of the edges, the ''load'' of a node $v\in V$ is its number of incoming edges. An edge $e$ is then said to be ''happy'' if switching its orientation does not make it point to a smaller-node load. | ||
One can show by a greedy argument that there always exists an orientation making all edges happy. Moreover, a surprising result established that, in the LOCAL model, such a configuration could be found in $\operatorname{poly}(\Delta)$ rounds, ''independent'' of the number of nodes $n$. However, the question of the dependence on $\Delta$ remains wide open, as even a $\operatorname{poly}\!\log(\Delta)$ upper bound is not ruled out. | One can show by a greedy argument that there always exists an orientation making all edges happy. Moreover, a surprising result established that, in the LOCAL model, such a configuration could be found in $\operatorname{poly}(\Delta)$ rounds, ''independent'' of the number of nodes $n$. However, the question of the dependence on $\Delta$ remains wide open, as even a $\operatorname{poly}\!\log(\Delta)$ upper bound is not ruled out. | ||
'''Question:''' What is the right dependence on $\Delta$? Can one show ''any'' lower polynomial lower bound, e.g., $\Delta^{0.1}$, $\sqrt{\Delta}$, or $\Delta$? | '''Question:''' What is the right dependence on $\Delta$? Can one show ''any'' lower polynomial lower bound, e.g., $\Delta^{0.1}$, $\sqrt{\Delta}$, or $\Delta$? | ||
