論文の概要: Towards Fairness in Online Service with k Servers and its Application on
Fair Food Delivery
- arxiv url: http://arxiv.org/abs/2312.11280v1
- Date: Mon, 18 Dec 2023 15:22:03 GMT
- ステータス: 処理完了
- システム内更新日: 2023-12-20 19:45:30.708276
- Title: Towards Fairness in Online Service with k Servers and its Application on
Fair Food Delivery
- Title(参考訳): kサーバによるオンラインサービスにおける公正性と公正食品配送への応用
- Authors: Daman Deep Singh, Amit Kumar, Abhijnan Chakraborty
- Abstract要約: 我々は k-FOOD 問題という仮定を使わずに k- の現実的な一般化を導入する。
k-FOOD問題は、フードデリバリー、ライドシェアリング、クイックコマースなど、さまざまな現実世界のユースケースをモデル化する汎用性を提供する。
オンラインプラットフォームにおける公平性の必要性に感銘を受けて、最大値の目的を持つFAIR k-FOOD問題を導入する。
- 参考スコア(独自算出の注目度): 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.
- Abstract(参考訳): k-SERVER問題(k-SERVER problem)は、いくつかの変種と拡張を持つオンラインアルゴリズムにおいて最も顕著な問題の1つである。
しかしながら、即時サーバの動作やサービス時間ゼロといった仮定を単純化することは、現実の問題への適用性を制限している。
本稿では,そのような前提を満たさないk-サーバの現実的な一般化について紹介する。k-food問題とは,送信先の位置と関連するピックアップタイムウインドウに関する要求がオンライン形式で到着し,それぞれが利用可能なkサーバの1つで提供されなければならないという問題である。
k-FOOD問題は、フードデリバリー、ライドシェアリング、クイックコマースなど、さまざまな現実世界のユースケースをモデル化する汎用性を提供する。
さらに,オンラインプラットフォームにおける公平性の必要性に動機づけられ,fair k-food問題をmax-min目的に導入する。
k-food問題とfair k-food問題の両方がnp-hardであり、時間拡張フローネットワークから自然に発生する最適なオフラインアルゴリズムを開発する。
次に,サーバの仮想移動を最寄りの要求位置へ伝達するオンラインアルゴリズムdoc4foodを提案する。
合成データセットと共に実世界の食品配送データセットに関する実験は、最先端のフードデリバリーアルゴリズムに対する提案アルゴリズムの有効性を確立した。
関連論文リスト
- From Canteen Food to Daily Meals: Generalizing Food Recognition to More
Practical Scenarios [92.58097090916166]
DailyFood-172とDailyFood-16という2つの新しいベンチマークを、毎日の食事から食のイメージをキュレートする。
これらの2つのデータセットは、よく計算された食品画像領域から日常的な食品画像領域へのアプローチの伝達性を評価するために使用される。
論文 参考訳(メタデータ) (2024-03-12T08:32:23Z) - Offline Inverse RL: New Solution Concepts and Provably Efficient
Algorithms [26.539011770169225]
逆強化学習(IRL)は、行動の実証から専門家の報酬機能を回復することを目的としている。
本稿では、オフライン設定の機会と限界を捉えた、実現可能な報酬セットという新しい概念を紹介する。
論文 参考訳(メタデータ) (2024-02-23T15:49:46Z) - On the Role of Server Momentum in Federated Learning [85.54616432098706]
a)フェデレートラーニング(FL)において未探索な大量のモーメントスキームを網羅するサーバモーメントの一般的な枠組みを提案する。
提案するフレームワークに対して厳密な収束解析を行う。
論文 参考訳(メタデータ) (2023-12-19T23:56:49Z) - Adaptive Resource Allocation for Virtualized Base Stations in O-RAN with
Online Learning [60.17407932691429]
基地局(vBS)を備えたオープンラジオアクセスネットワークシステムは、柔軟性の向上、コスト削減、ベンダーの多様性、相互運用性のメリットを提供する。
本研究では,予期せぬ「混み合う」環境下であっても,効率的なスループットとvBSエネルギー消費のバランスをとるオンライン学習アルゴリズムを提案する。
提案手法は, 課題のある環境においても, 平均最適性ギャップをゼロにすることで, サブ線形後悔を実現する。
論文 参考訳(メタデータ) (2023-09-04T17:30:21Z) - A Framework for Multi-stage Bonus Allocation in meal delivery Platform [14.64089765133449]
食事提供プラットフォームにおける多段階のボーナスアロケーション問題に対処する枠組みを提案する。
提案するフレームワークは,半ブラックボックスの受け入れ確率モデル,ラグランジアンデュアルベース動的プログラミングアルゴリズム,オンラインアロケーションアルゴリズムから構成される。
その結果,提案手法を用いることで,全体の注文キャンセルを25%以上削減できることがわかった。
論文 参考訳(メタデータ) (2022-02-22T06:52:34Z) - Low-Latency Federated Learning over Wireless Channels with Differential
Privacy [142.5983499872664]
フェデレートラーニング(FL)では、モデルトレーニングはクライアントに分散し、ローカルモデルは中央サーバによって集約される。
本稿では,各クライアントの差分プライバシ(DP)要件だけでなく,全体としてのトレーニング性能に制約された無線チャネル上でのFLトレーニング遅延を最小限に抑えることを目的とする。
論文 参考訳(メタデータ) (2021-06-20T13:51:18Z) - A Deep Reinforcement Learning Approach for the Meal Delivery Problem [1.5391321019692434]
一日に一組の宅配業者に与えられた動的顧客要求を満たす食事配達サービスについて検討する。
私たちはこのサービスをマルコフ決定プロセスとしてモデル化し、ソリューションアプローチとして深層強化学習を使用します。
本研究は,ある日に異なる順序周波数のクーリエの割り当てプロセスと最適なクーリエ数の両方について有意な知見を与える。
論文 参考訳(メタデータ) (2021-04-24T19:01:59Z) - Efficient Algorithms for Global Inference in Internet Marketplaces [6.2122699483618]
インターネット市場における供給需要のマッチングは、世界的な推論問題です。
近年まで、LP定式化によるWebスケールデータにおけるそのような問題の解決は難しかった。
最近の研究は、ポリトープの制約が単純であるような問題を解くための双対分解に基づくアプローチを開発した。
この研究では、これらの単純なポリトープを超えて、より複雑な構造化されたポリトープ制約を必要とする現実世界のインターネットマーケットプレイスを示す必要性を動機付けます。
論文 参考訳(メタデータ) (2021-03-09T08:00:58Z) - Group-Fair Online Allocation in Continuous Time [27.32936573198251]
公平性を考慮した継続的オンライン学習問題を考察する。
この定式化は、報酬最大化、最大値フェア、比例値アロケーションルールを回復させる。
本稿では,時間平均に対する二段階最適化に基づく新しいオンライン学習アルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-06-11T21:56:53Z) - Cross-Modal Food Retrieval: Learning a Joint Embedding of Food Images
and Recipes with Semantic Consistency and Attention Mechanism [70.85894675131624]
画像とレシピを共通の特徴空間に埋め込み、対応する画像とレシピの埋め込みが互いに近接するように学習する。
本稿では,2つのモダリティの埋め込みを正規化するためのセマンティック・一貫性とアテンション・ベース・ネットワーク(SCAN)を提案する。
食品画像や調理レシピの最先端のクロスモーダル検索戦略を,かなりの差で達成できることが示される。
論文 参考訳(メタデータ) (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)は、新興かつ有望なマルチメディアストリーミング技術であることを示した。
本稿では,サーバの限られた輸出帯域幅をマルチユーザに対して最適に割り当てるアルゴリズムを提案し,その品質・オブ・エクスペリエンス(QoE)を公平性で最大化する。
論文 参考訳(メタデータ) (2019-12-27T01:19:14Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。