Matched Queues with Matching Batch Pair (m, n)

• URL: http://arxiv.org/abs/2009.02742v4
• Date: Fri, 19 Mar 2021 07:23:08 GMT
• Title: Matched Queues with Matching Batch Pair (m, n)
• Authors: Heng-Li Liu, Quan-Lin Li, Chi Zhang
• Abstract summary: We show that this matched queue can be expressed as a novel bidirectional level-dependent quasi-birth-and-death process. We provide a detailed analysis for this matched queue, including the system stability, the average stationary queue lengthes, and the average sojourn time of any A- customer or B- customer.
• Score: 8.02548118934175
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we discuss an interesting but challenging bilateral stochastically matching problem: A more general matched queue with matching batch pair (m, n) and two types (i.e., types A and B) of impatient customers, where the arrivals of A- and B-customers are both Poisson processes, m A-customers and n B-customers are matched as a group which leaves the system immediately, and the customers' impatient behavior is to guarantee the stability of the system. We show that this matched queue can be expressed as a novel bidirectional level-dependent quasi-birth-and-death (QBD) process. Based on this, we provide a detailed analysis for this matched queue, including the system stability, the average stationary queue lengthes, and the average sojourn time of any A-customer or B-customer. We believe that the methodology and results developed in this paper can be applicable to dealing with more general matched queueing systems, which are widely encountered in various practical areas, for example, sharing economy, ridesharing platform, bilateral market, organ transplantation, taxi services, assembly systems, and so on.

Related papers

• Submodular Maximization Approaches for Equitable Client Selection in Federated Learning [4.167345675621377]
  In a conventional Learning framework, client selection for training typically involves the random sampling of a subset of clients in each iteration. This paper introduces two novel methods, namely SUBTRUNC and UNIONFL, designed to address the limitations of random client selection.
  arXiv  Detail & Related papers  (2024-08-24T22:40:31Z)
• Improving Bias Correction Standards by Quantifying its Effects on Treatment Outcomes [54.18828236350544]
  Propensity score matching (PSM) addresses selection biases by selecting comparable populations for analysis. Different matching methods can produce significantly different Average Treatment Effects (ATE) for the same task, even when meeting all validation criteria. To address this issue, we introduce a novel metric, A2A, to reduce the number of valid matches.
  arXiv  Detail & Related papers  (2024-07-20T12:42:24Z)
• Cohort Squeeze: Beyond a Single Communication Round per Cohort in Cross-Device Federated Learning [51.560590617691005]
  We investigate whether it is possible to squeeze more juice" out of each cohort than what is possible in a single communication round. Our approach leads to up to 74% reduction in the total communication cost needed to train a FL model in the cross-device setting.
  arXiv  Detail & Related papers  (2024-06-03T08:48:49Z)
• Learning-Based Pricing and Matching for Two-Sided Queues [14.854050478428727]
  We consider a dynamic system with multiple types of customers and servers. The arrival rate of each queue is determined by the price according to unknown demand or supply functions. This system can be used to model two-sided markets such as ride-sharing markets with passengers and drivers.
  arXiv  Detail & Related papers  (2024-03-17T05:07:04Z)
• Steady-State Analysis and Online Learning for Queues with Hawkes Arrivals [34.59794670349187]
  We investigate the long-run behavior of single-server queues with Hawkes arrivals and general service distributions. We develop an efficient numerical algorithm to solve the optimal staffing problem for the Hawkes queues in a data-driven manner.
  arXiv  Detail & Related papers  (2023-11-05T06:46:26Z)
• Towards Distribution-Agnostic Generalized Category Discovery [51.52673017664908]
  Data imbalance and open-ended distribution are intrinsic characteristics of the real visual world. We propose a Self-Balanced Co-Advice contrastive framework (BaCon) BaCon consists of a contrastive-learning branch and a pseudo-labeling branch, working collaboratively to provide interactive supervision to resolve the DA-GCD task.
  arXiv  Detail & Related papers  (2023-10-02T17:39:58Z)
• Quantifying the Cost of Learning in Queueing Systems [4.784875233446591]
  Cost of Learning in Queueing (CLQ) is a new metric that quantifies the maximum increase in time-averaged queue length caused by parameter uncertainty. We propose a unified analysis framework for CLQ that bridges Lyapunov and bandit analysis, provides guarantees for a wide range of algorithms, and could be of independent interest.
  arXiv  Detail & Related papers  (2023-08-15T14:50:12Z)
• Fed-CBS: A Heterogeneity-Aware Client Sampling Mechanism for Federated Learning via Class-Imbalance Reduction [76.26710990597498]
  We show that the class-imbalance of the grouped data from randomly selected clients can lead to significant performance degradation. Based on our key observation, we design an efficient client sampling mechanism, i.e., Federated Class-balanced Sampling (Fed-CBS) In particular, we propose a measure of class-imbalance and then employ homomorphic encryption to derive this measure in a privacy-preserving way.
  arXiv  Detail & Related papers  (2022-09-30T05:42:56Z)
• Efficient decentralized multi-agent learning in asymmetric bipartite queueing systems [6.069611493148631]
  We study decentralized multi-agent learning in bipartite queueing systems. In particular, N agents request service from K servers in a fully decentralized way. We provide a simple learning algorithm that, when run decentrally by each agent, leads the queueing system to have efficient performance.
  arXiv  Detail & Related papers  (2022-06-05T17:22:29Z)
• Tradeoffs in Sentence Selection Techniques for Open-Domain Question Answering [54.541952928070344]
  We describe two groups of models for sentence selection: QA-based approaches, which run a full-fledged QA system to identify answer candidates, and retrieval-based models, which find parts of each passage specifically related to each question. We show that very lightweight QA models can do well at this task, but retrieval-based models are faster still.
  arXiv  Detail & Related papers  (2020-09-18T23:39:15Z)
• Towards Model-Agnostic Post-Hoc Adjustment for Balancing Ranking Fairness and Algorithm Utility [54.179859639868646]
  Bipartite ranking aims to learn a scoring function that ranks positive individuals higher than negative ones from labeled data. There have been rising concerns on whether the learned scoring function can cause systematic disparity across different protected groups. We propose a model post-processing framework for balancing them in the bipartite ranking scenario.
  arXiv  Detail & Related papers  (2020-06-15T10:08:39Z)

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.