2 Search Results for "Udwani, Rajan"

Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2021.13
Secretary Matching Meets Probing with Commitment

Authors: Allan Borodin, Calum MacRury, and Akash Rakheja

Published in: LIPIcs, Volume 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)

Abstract
We consider the online bipartite matching problem within the context of stochastic probing with commitment. This is the one-sided online bipartite matching problem where edges adjacent to an online node must be probed to determine if they exist based on edge probabilities that become known when an online vertex arrives. If a probed edge exists, it must be used in the matching. We consider the competitiveness of online algorithms in the adversarial order model (AOM) and the secretary/random order model (ROM). More specifically, we consider an unknown bipartite stochastic graph G = (U,V,E) where U is the known set of offline vertices, V is the set of online vertices, G has edge probabilities (p_{e})_{e ∈ E}, and G has edge weights (w_{e})_{e ∈ E} or vertex weights (w_u)_{u ∈ U}. Additionally, G has a downward-closed set of probing constraints (𝒞_{v})_{v ∈ V}, where 𝒞_v indicates which sequences of edges adjacent to an online vertex v can be probed. This model generalizes the various settings of the classical bipartite matching problem (i.e. with and without probing). Our contributions include the introduction and analysis of probing within the random order model, and our generalization of probing constraints which includes budget (i.e. knapsack) constraints. Our algorithms run in polynomial time assuming access to a membership oracle for each 𝒞_v. In the vertex weighted setting, for adversarial order arrivals, we generalize the known 1/2 competitive ratio to our setting of 𝒞_v constraints. For random order arrivals, we show that the same algorithm attains an asymptotic competitive ratio of 1-1/e, provided the edge probabilities vanish to 0 sufficiently fast. We also obtain a strict competitive ratio for non-vanishing edge probabilities when the probing constraints are sufficiently simple. For example, if each 𝒞_v corresponds to a patience constraint 𝓁_v (i.e., 𝓁_v is the maximum number of probes of edges adjacent to v), and any one of following three conditions is satisfied (each studied in previous papers), then there is a conceptually simple greedy algorithm whose competitive ratio is 1-1/e. - When the offline vertices are unweighted. - When the online vertex probabilities are "vertex uniform"; i.e., p_{u,v} = p_v for all (u,v) ∈ E. - When the patience constraint 𝓁_v satisfies 𝓁_v ∈ {[1,|U|} for every online vertex; i.e., every online vertex either has unit or full patience. Finally, in the edge weighted case, we match the known optimal 1/e asymptotic competitive ratio for the classic (i.e. without probing) secretary matching problem.
Cite as

Allan Borodin, Calum MacRury, and Akash Rakheja. Secretary Matching Meets Probing with Commitment. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 13:1-13:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{borodin_et_al:LIPIcs.APPROX/RANDOM.2021.13,
  author =	{Borodin, Allan and MacRury, Calum and Rakheja, Akash},
  title =	{{Secretary Matching Meets Probing with Commitment}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)},
  pages =	{13:1--13:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-207-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{207},
  editor =	{Wootters, Mary and Sanit\`{a}, Laura},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2021.13},
  URN =		{urn:nbn:de:0030-drops-147067},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2021.13},
  annote =	{Keywords: Stochastic probing, Online algorithms, Bipartite matching, Optimization under uncertainty}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2019.25
Robust Appointment Scheduling with Heterogeneous Costs

Authors: Andreas S. Schulz and Rajan Udwani

Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)

Abstract
Designing simple appointment systems that under uncertainty in service times, try to achieve both high utilization of expensive medical equipment and personnel as well as short waiting time for patients, has long been an interesting and challenging problem in health care. We consider a robust version of the appointment scheduling problem, introduced by Mittal et al. (2014), with the goal of finding simple and easy-to-use algorithms. Previous work focused on the special case where per-unit costs due to under-utilization of equipment/personnel are homogeneous i.e., costs are linear and identical. We consider the heterogeneous case and devise an LP that has a simple closed-form solution. This solution yields the first constant-factor approximation for the problem. We also find special cases beyond homogeneous costs where the LP leads to closed form optimal schedules. Our approach and results extend more generally to convex piece-wise linear costs. For the case where the order of patients is changeable, we focus on linear costs and show that the problem is strongly NP-hard when the under-utilization costs are heterogeneous. For changeable order with homogeneous under-utilization costs, it was previously shown that an EPTAS exists. We instead find an extremely simple, ratio-based ordering that is 1.0604 approximate.
Cite as

Andreas S. Schulz and Rajan Udwani. Robust Appointment Scheduling with Heterogeneous Costs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 25:1-25:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{schulz_et_al:LIPIcs.APPROX-RANDOM.2019.25,
  author =	{Schulz, Andreas S. and Udwani, Rajan},
  title =	{{Robust Appointment Scheduling with Heterogeneous Costs}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
  pages =	{25:1--25:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-125-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{145},
  editor =	{Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.25},
  URN =		{urn:nbn:de:0030-drops-112407},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2019.25},
  annote =	{Keywords: Appointment scheduling, approximation algorithms, robust optimization}
}
  • Refine by Author
  • 1 Borodin, Allan
  • 1 MacRury, Calum
  • 1 Rakheja, Akash
  • 1 Schulz, Andreas S.
  • 1 Udwani, Rajan

  • Refine by Classification
  • 1 Theory of computation → Approximation algorithms analysis
  • 1 Theory of computation → Design and analysis of algorithms
  • 1 Theory of computation → Discrete optimization
  • 1 Theory of computation → Scheduling algorithms

  • Refine by Keyword
  • 1 Appointment scheduling
  • 1 Bipartite matching
  • 1 Online algorithms
  • 1 Optimization under uncertainty
  • 1 Stochastic probing
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2019
  • 1 2021

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact