-
作者：Friggstad, Zachary; Mousavi, Ramin; Rahgoshay, Mirmahdi; Salavatipour, Mohammad R.
作者单位：University of Alberta
摘要：In this paper, we present improved approximation algorithms for the (unsplitta-ble) capacitated vehicle routing problem (CVRP) in general metrics. In the CVRP, we are given a set of points (clients) V together with a depot r in a metric space, with each v is an element of V having a demand d(v) > 0 and a vehicle of bounded capacity Q. The goal is to find a mini-mum cost collection of tours for the vehicle, each starting and ending at the depot, such that each client is visited at least once an...
-
作者：Ding, Jian; Li, Zhangsong
作者单位：Peking University
摘要：We propose an efficient algorithm for matching two correlated Erdos-Renyi graphs with n vertices whose edges are correlated through a latent vertex correspondence. When the edge density q = n(-alpha+o(1)) for a constant alpha is an element of[0, 1), we show that our algorithm has polynomial running time and succeeds to recover the latent matching as long as the edge correlation is nonvanishing. This is closely related to our previous work on a polynomialtime algorithm that matches two Gaussian...
-
作者：Lammel, Sebastian; Shikhman, Vladimir
作者单位：Technische Universitat Chemnitz
摘要：For mathematical programs with complementarity constraints (MPCC), we study the stability properties of their Scholtes regularization. Our goal is to relate nondegenerate C-stationary points of MPCC with nondegenerate Karush-Kuhn-Tucker points of the Scholtes regularization up to their topological type. As it is standard in the framework of Morse theory, the topological types are captured by the C-index and the quadratic index, respectively. It turns out that a change of the topological type f...
-
作者：Delarue, Francois; Vasileiadis, Athanasios
作者单位：Universite Cote d'Azur; Centre National de la Recherche Scientifique (CNRS)
摘要：The goal of this paper is to demonstrate that common noise may serve as an exploration noise for learning the solution of a mean field game. This concept is here exemplified through a toy linear-quadratic model, for which a suitable form of common noise has already been proven to restore existence and uniqueness. We here go one step further and prove that the same form of common noise may force the convergence of the learning algorithm called fictitious play, and this without any further poten...
-
作者：Guo, Feng; Wang, Jie; Zheng, Jianhao
作者单位：Dalian University of Technology; Chinese Academy of Sciences; Academy of Mathematics & System Sciences, CAS
摘要：This paper is devoted to the problem of minimizing a sum of rational functions over a basic semialgebraic set. We provide a hierarchy of sum-of-squares (SOS) relaxations that is dual to the generalized moment problem approach proposed by Bugarin, Henrion, and Lasserre. The investigation of the dual SOS aspect offers two benefits: (1) it allows us to conduct a convergence rate analysis for the hierarchy; (2) it leads to a sign symmetry-adapted hierarchy consisting of block-diagonal semidefinite...
-
作者：Atar, Rami; Ichiba, Tomoyuki
作者单位：Technion Israel Institute of Technology; University of California System; University of California Santa Barbara
摘要：Banerjee, Budhiraja and Estevez (2025) studied a randomized load balancing model in a heavy traffic asymptotic regime where the load balancing stream is thin compared to the total arrival stream. It was shown that the limit is given by a system of rankbased Brownian particles on the half-line. In this paper we extend this result from the case of exponential service time to an invariance principle, where service times have finite second moment. The main tool is a new notion of rank-based stocha...
-
作者：Kavitha, Telikepalli; Makino, Kazuhisa
作者单位：Tata Institute of Fundamental Research (TIFR); Tata Institute of Fundamental Research (TIFR), Mumbai; Kyoto University
摘要：We consider a matching problem in a hospitals/residents instance G, that is, a many-to-one matching instance, in which every vertex has a strict ranking of its neighbors and hospitals have capacities. A matching M is said to be popular if M does not lose an election against any matching in which vertices cast votes for one matching versus another. There are efficient algorithms to find popular matchings in G, but it is NP-hard to find a min-cost popular matching when edges have costs. When pre...
-
作者：Gaspard, Mallory E.; Vladimirsky, Alexander
作者单位：Cornell University; Cornell University
摘要：When traveling through a graph with an accessible deterministic path to a target, is it ever preferable to resort to stochastic node-to-node transitions instead? And, if so, what are the conditions guaranteeing that such a stochastic optimal routing policy can be computed efficiently? We aim to answer these questions here by defining a class of Opportunistically Stochastic Shortest Path (OSSP) problems and deriving sufficient conditions for applicability of noniterative label-setting methods. ...
-
作者：Liang, Jiaxin (alys); Jasin, Stefanus; Uichanco, Joline
作者单位：McGill University; University of Michigan System; University of Michigan; New York University; New York University Tandon School of Engineering
摘要：This paper addresses operational challenges faced by retailers offering free return policies. We consider a general system with lost sales, positive lead time, periodic review, binomial demand, and an arbitrary restriction on price change frequency. We study the joint pricing and inventory decisions in the presence of stochastic returns. Specifically, when an item is purchased, it can be returned at a future random time and may be restocked for resale after passing an inspection. We assume a g...
-
作者：Fikioris, Giannis; Tardos, Eva
作者单位：Cornell University
摘要：Bandits with knapsacks (BwK), the generalization of the multiarmed bandits problem under global budget constraints, has received a lot of attention in recent years. It has numerous applications, including dynamic pricing, repeated auctions, ad allocation, network scheduling, etc. Previous work focuses on one of the two extremes: stochastic BwK in which the rewards and consumptions of the resources of each round are sampled from an independent and identical distribution and adversarial BwK in w...
