Integrated Optimization of Bipartite Matching and Its Stochastic Behavior: New Formulation and Approximation Algorithm via Min-cost Flow Optimization

Authors

  • Yuya Hikima NTT Service Evolution Laboratories, NTT Corporation
  • Yasunori Akagi NTT Service Evolution Laboratories, NTT Corporation
  • Hideaki Kim NTT Service Evolution Laboratories, NTT Corporation
  • Masahiro Kohjima NTT Service Evolution Laboratories, NTT Corporation
  • Takeshi Kurashima NTT Service Evolution Laboratories, NTT Corporation
  • Hiroyuki Toda NTT Service Evolution Laboratories, NTT Corporation

Keywords:

Constraint Optimization, Applications

Abstract

The research field of stochastic matching has yielded many developments for various applications. In most stochastic matching problems, the probability distributions inherent in the nodes and edges are set a priori, and are not controllable. However, many matching services have options, which we call control variables, that affect the probability distributions and thus what constitutes an optimum matching. Although several methods for optimizing the values of the control variables have been developed, their optimization in consideration of the matching problem is still in its infancy. In this paper, we formulate an optimization problem for determining the values of the control variables so as to maximize the expected value of matching weights. Since this problem involves hard to evaluate objective values and is non-convex, we construct an approximation algorithm via a minimum-cost flow algorithm that can find 3-approximation solutions rapidly. Simulations on real data from a ride-hailing platform and a crowd-sourcing market show that the proposed method can find solutions with high profits of the service provider in practical time.

Downloads

Published

2021-05-18

How to Cite

Hikima, Y., Akagi, Y., Kim, H., Kohjima, M., Kurashima, T., & Toda, H. (2021). Integrated Optimization of Bipartite Matching and Its Stochastic Behavior: New Formulation and Approximation Algorithm via Min-cost Flow Optimization. Proceedings of the AAAI Conference on Artificial Intelligence, 35(5), 3796-3805. Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/16497

Issue

Section

AAAI Technical Track on Constraint Satisfaction and Optimization