2 Search Results for "Orlin, James B."

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.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}
}
Document
DOI: 10.4230/DagSemProc.10171.2
Improved Algorithms for Computing Fisher's Market Clearing Prices

Authors: James B. Orlin

Published in: Dagstuhl Seminar Proceedings, Volume 10171, Equilibrium Computation (2010)

Abstract
We give the first strongly polynomial time algorithm for computing an equilibrium for the linear utilities case of Fisher's market model. We consider a problem with a set $B$ of buyers and a set $G$ of divisible goods. Each buyer $i$ starts with an initial integral allocation $e_i$ of money. The integral utility for buyer $i$ of good $j$ is $U_{ij}$. We first develop a weakly polynomial time algorithm that runs in $O(n^4 log U_{max} + n^3 e_{max})$ time, where $n = |B| + |G|$. We further modify the algorithm so that it runs in $O(n^4 log n)$ time. These algorithms improve upon the previous best running time of $O(n^8 log U_{max} + n^7 log e_{max})$, due to Devanur et al.
Cite as

James B. Orlin. Improved Algorithms for Computing Fisher's Market Clearing Prices. In Equilibrium Computation. Dagstuhl Seminar Proceedings, Volume 10171, pp. 1-19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{orlin:DagSemProc.10171.2,
  author =	{Orlin, James B.},
  title =	{{Improved Algorithms for Computing Fisher's Market Clearing Prices}},
  booktitle =	{Equilibrium Computation},
  pages =	{1--19},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10171},
  editor =	{Edith Elkind and Nimrod Megiddo and Peter Bro Miltersen and Vijay V. Vazirani and Bernahrd von Stengel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.10171.2},
  URN =		{urn:nbn:de:0030-drops-26720},
  doi =		{10.4230/DagSemProc.10171.2},
  annote =	{Keywords: Market equilibrium, Fisher, strongly polynomial}
}
  • Refine by Author
  • 1 Orlin, James B.
  • 1 Schulz, Andreas S.
  • 1 Udwani, Rajan

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

  • Refine by Keyword
  • 1 Appointment scheduling
  • 1 Fisher
  • 1 Market equilibrium
  • 1 approximation algorithms
  • 1 robust optimization
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2010
  • 1 2019

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 Schloss Dagstuhl - LZI GmbH Imprint Privacy Contact