Arrow Research search

Author name cluster

Esther M. Arkin

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

10 papers
2 author rows

Possible papers

10

I&C Journal 2003 Journal Article

The Lazy Bureaucrat scheduling problem

  • Esther M. Arkin
  • Michael A. Bender
  • Joseph S.B. Mitchell
  • Steven S. Skiena

We introduce a new class of scheduling problems in which the optimization is performed by the worker (single “machine”) who performs the tasks. A typical worker’s objective is to minimize the amount of work he does (he is “lazy”), or more generally, to schedule as inefficiently (in some sense) as possible. The worker is subject to the constraint that he must be busy when there is work that he can do; we make this notion precise both in the preemptive and nonpreemptive settings. The resulting class of “perverse” scheduling problems, which we denote “Lazy Bureaucrat Problems, ” gives rise to a rich set of new questions that explore the distinction between maximization and minimization in computing optimal schedules.

Details DOI

FOCS Conference 1992 Conference Paper

Computing a Shortest k-Link Path in a Polygon

  • Joseph S. B. Mitchell
  • Christine D. Piatko
  • Esther M. Arkin

The authors consider the problem of finding a shortest polygonal path from s to t within a simple polygon P, subject to the restriction that the path have at most k links (edges). They give an algorithm to compute a k-link path with length at most (1 + epsilon ) times the length of a shortest k-link path, for any error tolerance epsilon >0. The algorithm runs in time O(n/sup 3/k/sup 3/ log (Hk/ epsilon /sup 1/k/)), where N is the largest integer coordinate among the n vertices of P. They also study the more general problem of approximating shortest k-link paths in polygons with holes. In this case, they give an algorithm that returns a path with at most 2k links and length at most that of a shortest k-link path; the running time is O(kE/sup 2/), where E is the number of edges in the visibility graph. Finally, they study the bicriteria path problem in which the two criteria are link length and 'total turn' (the integral of mod Delta theta mod along a path). They obtain in an exact polynomial-time algorithm for polygons with holes. >

Details
v2026.09.13