{"id":170,"date":"2014-12-06T11:40:12","date_gmt":"2014-12-06T11:40:12","guid":{"rendered":"http:\/\/meyn.coron.us\/?page_id=170"},"modified":"2026-04-14T09:56:21","modified_gmt":"2026-04-14T14:56:21","slug":"optimization-of-dynamic-matching-models","status":"publish","type":"page","link":"https:\/\/faculty.eng.ufl.edu\/meyn\/publications\/optimization-of-dynamic-matching-models\/","title":{"rendered":"Optimization of Dynamic Matching Models"},"content":{"rendered":"\n\n\n\n\n\n
\n

Optimization of Dynamic \u00a0Matching Models<\/a><\/h3>\n

Ana Bu\u0161i\u0107 and Sean Meyn<\/p>\n<\/td>\n

<\/td>\n<\/tr>\n
\n
We consider a discrete-time bipartite matching model with random arrivals of units of supply and demand that can wait in queues located at the nodes in the network. A control policy determines which are matched at each time. The focus is on the infinite-horizon average-cost optimal control problem.<\/span><\/div>\n

\nA relaxation of the stochastic control problem is proposed, which is found to be a special case of an inventory model, as treated in the classical theory of Clark and Scarf. The optimal policy for the relaxation admits a closed-form expression. Based on the policy for this relaxation, a new matching policy is proposed. For a parameterized family of models in which the network load approaches capacity, this policy is shown to be approximately optimal, with bounded regret, even though the average cost grows without bound. <\/span><\/div>\n
<\/div>\n
\n
\n
@article{busmey14,<\/div>\n
author = {A.~Bu\\v{s}i\\'{c} and S. Meyn},<\/div>\n
title = {{Optimization of Dynamic Matching Models}},<\/div>\n
journal = {ArXiv e-prints},<\/div>\n<\/div>\n<\/div>\n
\n
volume = {abs\/1411.1044},Month = {Nov.},<\/div>\n
year = {2014}}<\/div>\n<\/div>\n<\/td>\n
\n
\n

\"NNv2\"<\/a><\/p>\n<\/div>\n

\n
\n

\"costThresholdsAndCompare\"<\/a><\/p>\n<\/div>\n<\/td>\n<\/tr>\n

On the right is the threshold policy for various values of of the threshold tau. The optimal threshold is very close to the value predicted by the RBM model. The plots on the right hand side compare the average cost obtained using the threshold policy (using the diffusion heuristic), MaxWeight, and a priority policy<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n","protected":false},"excerpt":{"rendered":"

Optimization of Dynamic \u00a0Matching Models Ana Bu\u0161i\u0107 and Sean Meyn We consider a discrete-time bipartite matching model with random arrivals of units of supply and demand that can wait in queues located at the nodes in the network. A control policy determines which are matched at each time. The focus is on the infinite-horizon average-cost […]<\/p>\n","protected":false},"author":1347,"featured_media":0,"parent":27,"menu_order":2,"comment_status":"closed","ping_status":"closed","template":"page-templates\/page-section-nav.php","meta":{"_acf_changed":false,"inline_featured_image":false,"featured_post":"","footnotes":"","_links_to":"","_links_to_target":""},"class_list":["post-170","page","type-page","status-publish","hentry"],"acf":[],"_links":{"self":[{"href":"https:\/\/faculty.eng.ufl.edu\/meyn\/wp-json\/wp\/v2\/pages\/170","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/faculty.eng.ufl.edu\/meyn\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/faculty.eng.ufl.edu\/meyn\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/faculty.eng.ufl.edu\/meyn\/wp-json\/wp\/v2\/users\/1347"}],"replies":[{"embeddable":true,"href":"https:\/\/faculty.eng.ufl.edu\/meyn\/wp-json\/wp\/v2\/comments?post=170"}],"version-history":[{"count":1,"href":"https:\/\/faculty.eng.ufl.edu\/meyn\/wp-json\/wp\/v2\/pages\/170\/revisions"}],"predecessor-version":[{"id":2911,"href":"https:\/\/faculty.eng.ufl.edu\/meyn\/wp-json\/wp\/v2\/pages\/170\/revisions\/2911"}],"up":[{"embeddable":true,"href":"https:\/\/faculty.eng.ufl.edu\/meyn\/wp-json\/wp\/v2\/pages\/27"}],"wp:attachment":[{"href":"https:\/\/faculty.eng.ufl.edu\/meyn\/wp-json\/wp\/v2\/media?parent=170"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}