Towards Fairness in Online Service with k Servers and its Application on Fair Food Delivery

• URL: http://arxiv.org/abs/2312.11280v1
• Date: Mon, 18 Dec 2023 15:22:03 GMT
• Title: Towards Fairness in Online Service with k Servers and its Application on Fair Food Delivery
• Authors: Daman Deep Singh, Amit Kumar, Abhijnan Chakraborty
• Abstract summary: We introduce a realistic generalization of k- without its assumptions - the k-FOOD problem. The k-FOOD problem offers the versatility to model a variety of real-world use cases such as food delivery, ride sharing, and quick commerce. Motivated by the need for fairness in online platforms, we introduce the FAIR k-FOOD problem with the max-min objective.
• Score: 6.729646573556134
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The k-SERVER problem is one of the most prominent problems in online algorithms with several variants and extensions. However, simplifying assumptions like instantaneous server movements and zero service time has hitherto limited its applicability to real-world problems. In this paper, we introduce a realistic generalization of k-SERVER without such assumptions - the k-FOOD problem, where requests with source-destination locations and an associated pickup time window arrive in an online fashion, and each has to be served by exactly one of the available k servers. The k-FOOD problem offers the versatility to model a variety of real-world use cases such as food delivery, ride sharing, and quick commerce. Moreover, motivated by the need for fairness in online platforms, we introduce the FAIR k-FOOD problem with the max-min objective. We establish that both k-FOOD and FAIR k-FOOD problems are strongly NP-hard and develop an optimal offline algorithm that arises naturally from a time-expanded flow network. Subsequently, we propose an online algorithm DOC4FOOD involving virtual movements of servers to the nearest request location. Experiments on a real-world food-delivery dataset, alongside synthetic datasets, establish the efficacy of the proposed algorithm against state-of-the-art fair food delivery algorithms.

Related papers

• Learning to Solve Combinatorial Optimization under Positive Linear Constraints via Non-Autoregressive Neural Networks [103.78912399195005]
  Combinatorial optimization (CO) is the fundamental problem at the intersection of computer science, applied mathematics, etc. In this paper, we design a family of non-autoregressive neural networks to solve CO problems under positive linear constraints. We validate the effectiveness of this framework in solving representative CO problems including facility location, max-set covering, and traveling salesman problem.
  arXiv  Detail & Related papers  (2024-09-06T14:58:31Z)
• The Restaurant Meal Delivery Problem with Ghost Kitchens [0.0]
  "Ghost kitchens" proposes synchronized food preparation of several restaurants in a central complex. We propose operational strategies for the effective operations of ghost kitchens. We show that both integrated optimization of cook scheduling and dispatching vehicle, as well as anticipation of future demand and decisions, are essential for successful operations.
  arXiv  Detail & Related papers  (2024-08-14T09:54:03Z)
• RoDE: Linear Rectified Mixture of Diverse Experts for Food Large Multi-Modal Models [96.43285670458803]
  Uni-Food is a unified food dataset that comprises over 100,000 images with various food labels. Uni-Food is designed to provide a more holistic approach to food data analysis. We introduce a novel Linear Rectification Mixture of Diverse Experts (RoDE) approach to address the inherent challenges of food-related multitasking.
  arXiv  Detail & Related papers  (2024-07-17T16:49:34Z)
• A Federated Online Restless Bandit Framework for Cooperative Resource Allocation [23.698976872351576]
  We study the cooperative resource allocation problem with unknown system dynamics of MRPs. We put forth a Federated Thompson-enabled Whittle Index (FedTSWI) algorithm to solve this multi-agent online RMAB problem. Numerical results show that the proposed algorithm achieves a fast convergence rate of $mathcalO(sqrtTlog(T))$ and better performance compared with baselines.
  arXiv  Detail & Related papers  (2024-06-12T08:34:53Z)
• From Canteen Food to Daily Meals: Generalizing Food Recognition to More Practical Scenarios [92.58097090916166]
  We present two new benchmarks, namely DailyFood-172 and DailyFood-16, designed to curate food images from everyday meals. These two datasets are used to evaluate the transferability of approaches from the well-curated food image domain to the everyday-life food image domain.
  arXiv  Detail & Related papers  (2024-03-12T08:32:23Z)
• Low-Latency Federated Learning over Wireless Channels with Differential Privacy [142.5983499872664]
  In federated learning (FL), model training is distributed over clients and local models are aggregated by a central server. In this paper, we aim to minimize FL training delay over wireless channels, constrained by overall training performance as well as each client's differential privacy (DP) requirement.
  arXiv  Detail & Related papers  (2021-06-20T13:51:18Z)
• A Deep Reinforcement Learning Approach for the Meal Delivery Problem [1.5391321019692434]
  We consider a meal delivery service fulfilling dynamic customer requests given a set of couriers over the course of a day. We model this service as a Markov decision process and use deep reinforcement learning as the solution approach. Our results present valuable insights on both the courier assignment process and the optimal number of couriers for different order frequencies on a given day.
  arXiv  Detail & Related papers  (2021-04-24T19:01:59Z)
• Efficient Algorithms for Global Inference in Internet Marketplaces [6.2122699483618]
  Matching demand to supply in internet marketplaces is a global inference problem. Until recently, solving such problems on web-scale data with an LP formulation was intractable. Recent work developed a dual decomposition-based approach to solve such problems when the polytope constraints are simple. In this work, we motivate the need to go beyond these simple polytopes and show real-world internet marketplaces that require more complex structured polytope constraints.
  arXiv  Detail & Related papers  (2021-03-09T08:00:58Z)
• Cross-Modal Food Retrieval: Learning a Joint Embedding of Food Images and Recipes with Semantic Consistency and Attention Mechanism [70.85894675131624]
  We learn an embedding of images and recipes in a common feature space, such that the corresponding image-recipe embeddings lie close to one another. We propose Semantic-Consistent and Attention-based Networks (SCAN), which regularize the embeddings of the two modalities through aligning output semantic probabilities. We show that we can outperform several state-of-the-art cross-modal retrieval strategies for food images and cooking recipes by a significant margin.
  arXiv  Detail & Related papers  (2020-03-09T07:41:17Z)
• Non-Cooperative Game Theory Based Rate Adaptation for Dynamic Video Streaming over HTTP [89.30855958779425]
  Dynamic Adaptive Streaming over HTTP (DASH) has demonstrated to be an emerging and promising multimedia streaming technique. We propose a novel algorithm to optimally allocate the limited export bandwidth of the server to multi-users to maximize their Quality of Experience (QoE) with fairness guaranteed.
  arXiv  Detail & Related papers  (2019-12-27T01:19:14Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.