We study a variation of the classical Pandora's problem in which a decision maker (DM) sequentially explores alternatives from a given set and learns their values while trying to acquire the best alternative. The ...
详细信息
We study a variation of the classical Pandora's problem in which a decision maker (DM) sequentially explores alternatives from a given set and learns their values while trying to acquire the best alternative. The variations in the model we study are (i) alternatives randomly become unavailable during exploration and (ii) the DM's ability to acquire a remaining alternative is uncertain and depends on a chosen offer price. Such acquisition uncertainties arise in many applications, including housing search, hiring problems, and e-commerce, but greatly complicate the search problem in that optimal policies retain all previously explored alternative values as part of the problem state, as opposed to only the highest explored value as in Pandora's rule. Our central insight is that despite the complexity that these acquisition uncertainties create, simple greedy policies based on static sequencing and a single threshold value enjoy strong performance guarantees. We develop such a class of policies and show how to compute them using a greedy algorithm whose worst-case run-time scales linearly (up to logarithmic factors) in the number of alternative types. We show that our policies (a) are asymptotically optimal in high multiplicity regimes with many alternatives and (b) obtain at least 1- e(-1) approximate to 63:2% of the optimal value under a broad set of conditions. Extensive numerical examples support this theory: We illustrate our policies on a variation of Pandora's problem with disappearing alternatives and housing search on models calibrated on data from the online brokerage Redfin. In these examples, our policies significantly outperform policies based on Pandora's rule.
We consider the vehicle routing problem with stochastic demands (VRPSD). We give randomized approximation algorithms achieving approximation guarantees of 1 + alpha for split-delivery VRPSD, and 2 + alpha for unsplit-...
详细信息
We consider the vehicle routing problem with stochastic demands (VRPSD). We give randomized approximation algorithms achieving approximation guarantees of 1 + alpha for split-delivery VRPSD, and 2 + alpha for unsplit-delivery VRPSD;here alpha is the best approximation guarantee for the traveling salesman problem. These bounds match the best known for even the respective deterministic problems [Altinkemer, K., B. Gavish. 1987. Heuristics for unequal weight delivery problems with a fixed error guarantee. Oper Res. Lett. 6(4) 149-158;Altinkemer, K., B. Gavish. 1990. Heuristics for delivery problems with constant error guarantees. Transportation Res. 24(4) 294-297] We also show that the "cyclic heuristic" for split-delivery VRPSD achieves a constant approximation ratio, as conjectured in Bertsimas [Bertsimas, D. J. 1992. A vehicle routing problem with stochastic demand. Oper Res. 40(3) 574-585].
In this paper, we consider the revenue management problem from the perspective of online algorithms. This approach eliminates the need for both demand forecasts and a risk-neutrality assumption. The competitive ratio ...
详细信息
In this paper, we consider the revenue management problem from the perspective of online algorithms. This approach eliminates the need for both demand forecasts and a risk-neutrality assumption. The competitive ratio of a policy relative to a given input sequence is the ratio of the policy's performance to the offline optimal. Under the online algorithm approach, revenue management policies are evaluated based on the highest competitive ratio they can guarantee. We are able to define lower bounds on the best-possible performance and describe policies that achieve these lower bounds. We address the two-fare problem in greatest detail, but also treat the general multifare problem and the bid-price control problem.
A notorious open problem in the field of rendezvous search is to decide the rendezvous value of the symmetric rendezvous search problem on the line, when the initial distance between the two players is two. We show th...
详细信息
A notorious open problem in the field of rendezvous search is to decide the rendezvous value of the symmetric rendezvous search problem on the line, when the initial distance between the two players is two. We show that the symmetric rendezvous value is within the interval (4.1520, 4.2574), which considerably improves the previous best-known result (3.9546, 4.3931). To achieve the improved bounds, we call upon results from absorbing Markov chain theory and mathematical programming theory-particularly fractional quadratic programming and semidefinite programming. Moreover, we also establish some important properties of this problem, which could be of independent interest and useful for resolving this problem completely. Finally, we conjecture that the symmetric rendezvous value is asymptotically equal to 4.25 based on our numerical calculations.
暂无评论