English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

A dynamic flow network $G$ with uniform capacity $c$ is a graph in which atmost $c$ units of flow can enter an edge in one time unit. If flow enters avertex faster than it can leave, congestion occurs. The evacuation problem isto evacuate all flow to sinks assuming that all flow is confluent, i.e., allflow passing through a particular vertex must follow the same exit edge. The$k$-sink location problem is to place $k$-sinks so as to minimize thisevacuation time. Although the $k$-sink location problem is NP-Hard on a generalgraph it can be solved in $\tilde O(k^2 n)$ time on trees.  The concept of minmax-regret arises from robust optimization. For eachsource, a range of possible flow values is provided and any scenario with flowvalues in those ranges might occur. The goal is to find a sink placement thatminimizes, over all possible scenarios, the difference between the evacuationtime to those sinks and the minimal evacuation time of that scenario.  The Minmax-Regret $k$-Sink Location on a Dynamic Path Networks with uniformcapacities is polynomial solvable in $n$ and $k$. Similarly, the Minmax-Regret$k$-center problem on trees is polynomial solvable in $n$ and $k$. Prior tothis work, polynomial time solutions to the Minmax-Regret $k$-Sink Location onDynamic Tree Networks with uniform capacities were only known for $k=1$. Thispaper solves this problem, for general $k,$ in time $$O\Bigl( \max(k^2,\log^2n)\, k^2 n^2 \log^5 n\Bigr).$$

Minmax-Regret $k$-Sink Location on a Dynamic Tree Network with Uniform Capacities