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/

Global: Zendy Plus annual

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

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We study a common delivery problem encountered in nowadays onlinefood-ordering platforms: Customers order dishes online, and the restaurantdelivers the food after receiving the order. Specifically, we study a problemwhere $k$ vehicles of capacity $c$ are serving a set of requests ordering foodfrom one restaurant. After a request arrives, it can be served by a vehiclemoving from the restaurant to its delivery location. We are interested inserving all requests while minimizing the maximum flow-time, i.e., the maximumtime length a customer waits to receive his/her food after submitting theorder.  We show that the problem is hard in both offline and online settings: Thereis a hardness of approximation of $\Omega(n)$ for the offline problem, and alower bound of $\Omega(n)$ on the competitive ratio of any online algorithm,where $n$ is number of points in the metric. Our main result is an$O(1)$-competitive online algorithm for the uncapaciated (i.e, $c = \infty$)food delivery problem on tree metrics. Then we consider the speed-augmentationmodel. We develop an exponential time $(1+\epsilon)$-speeding$O(1/\epsilon)$-competitive algorithm for any $\epsilon > 0$. A polynomial timealgorithm can be obtained with a speeding factor of $\alpha_{TSP}+ \epsilon$ or$\alpha_{CVRP}+ \epsilon$, depending on whether the problem is uncapacitated.Here $\alpha_{TSP}$ and $\alpha_{CVRP}$ are the best approximation factors forthe traveling salesman (TSP) and capacitated vehicle routing (CVRP) problemsrespectively. We complement the results with some negative ones.

Online Food Delivery to Minimize Maximum Flow Time