Author name cluster

Joseph S.B. Mitchell

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.

6 papers

1 author row

TCS Journal 2025 Journal Article

On some geometric optimization problems with segments

Joseph S.B. Mitchell
Supantha Pandit

We study three fundamental geometric optimization problems – INDEPENDENT SET, PIERCING SET, and DOMINATING SET – on sets of axis-parallel segments in the plane. We consider special cases in which the segments are either unit length or are anchored on an inclined line (a line with slope −1). When the segments are anchored on both sides, we prove that all three problems are NP-complete 2; NP-completeness was known for the corresponding problems with axis-parallel rectangles anchored on an inclined line (Correa et al. , 2015 [1], Mudgal and Pandit, 2015 [2], Pandit, 2017, [3]). Further, we prove that the DOMINATING SET problem with unit segments in the plane is NP-complete. When the input segments are anchored on one side of the inclined line, known polynomial-time algorithms can be used to solve the INDEPENDENT SET and PIERCING SET problems. We also discuss approximation and the discrete variants of some of the problems.

Details DOI

TCS Journal 2021 Journal Article

Minimum Membership Covering and Hitting

Joseph S.B. Mitchell
Supantha Pandit

Set Cover is a well-studied problem with application in many fields. A well-known variant of this problem is the Minimum Membership Set Cover problem: Given a set of points and a set of objects, the objective is to cover all points while minimizing the maximum number of objects that contain any one point. A dual of this problem is the Minimum Membership Hitting Set problem: Given a set of points and a set of objects, the objective is to stab all of the objects while minimizing the maximum number of points that an object contains. We study both of these variants in a geometric setting with various types of geometric objects in the plane, including axis-parallel line segments, axis-parallel strips, rectangles that are anchored on a horizontal line from one side, rectangles that are stabbed by a horizontal line, and rectangles that are anchored on one of two horizontal lines (i. e. , each rectangle shares its top or its bottom edge (or both) with one of the input horizontal lines). For each of these problems we either prove NP-hardness or we give a polynomial-time algorithm. In particular, we show that it is NP-complete to decide whether there exists a solution with depth exactly 1 for either the Minimum Membership Set Cover or the Minimum Membership Hitting Set problem. In addition, we study a generalized version of the Minimum Membership Hitting Set problem.

Details DOI

TCS Journal 2015 Journal Article

The minimum backlog problem

Michael A. Bender
Sándor P. Fekete
Alexander Kröller
Vincenzo Liberatore
Joseph S.B. Mitchell
Valentin Polishchuk
Jukka Suomela

We study the minimum backlog problem (MBP). This online problem arises, e. g. , in the context of sensor networks. We focus on two main variants of MBP. The discrete MBP is a 2-person game played on a graph G = ( V, E ). The player is initially located at a vertex of the graph. In each time step, the adversary pours a total of one unit of water into cups that are located on the vertices of the graph, arbitrarily distributing the water among the cups. The player then moves from her current vertex to an adjacent vertex and empties the cup at that vertex. The player's objective is to minimize the backlog, i. e. , the maximum amount of water in any cup at any time. The geometric MBP is a continuous-time version of the MBP: the cups are points in the two-dimensional plane, the adversary pours water continuously at a constant rate, and the player moves in the plane with unit speed. Again, the player's objective is to minimize the backlog. We show that the competitive ratio of any algorithm for the MBP has a lower bound of Ω ( D ), where D is the diameter of the graph (for the discrete MBP) or the diameter of the point set (for the geometric MBP). Therefore we focus on determining a strategy for the player that guarantees a uniform upper bound on the absolute value of the backlog. For the absolute value of the backlog there is a trivial lower bound of Ω ( D ), and the deamortization analysis of Dietz and Sleator gives an upper bound of O ( D log ⁡ N ) for N cups. Our main result is a tight upper bound for the geometric MBP: we show that there is a strategy for the player that guarantees a backlog of O ( D ), independently of the number of cups. We also study a localized version of the discrete MBP: the adversary has a location within the graph and must act locally (filling cups) with respect to his position, just as the player acts locally (emptying cups) with respect to her position. We prove that deciding the value of this game is PSPACE-hard.

Details DOI

I&C Journal 2012 Journal Article

Optimizing restriction site placement for synthetic genomes

Pablo Montes
Heraldo Memelli
Charles B. Ward
Joondong Kim
Joseph S.B. Mitchell
Steven Skiena

Restriction enzymes are the workhorses of molecular biology. We introduce a new problem which arises in the course of our project to design virus variants to serve as potential vaccines: we wish to modify virus-length genomes to introduce large numbers of unique restriction enzyme recognition sites while preserving wild-type function by substitution of synonymous codons. We show that the resulting problem is NP-Complete, give an exponential-time algorithm, as well as well-performing heuristics, and give excellent results for five sample viral genomes. Our resulting modified genomes have several times more unique restriction sites and reduce the maximum gap between adjacent sites by three to nine-fold.

Details DOI

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

AIJ Journal 1988 Journal Article

An algorithmic approach to some problems in terrain navigation

Joseph S.B. Mitchell

Recent advances in the field of computational geometry have provided efficient algorithms for a variety of shortest path problems. Many problems in the field of terrain navigation can be cast as optimal path problems in a precise geometric model. With such a model one can develop and analyze algorithms for the solution of the original problem and can gain insights into how to design more efficient heuristics to deal with more complex problems. We examine the path planning problem in which we are given a “map” of a region of terrain and we are expected to find optimal paths from one point to another. This, for example, is a task which must be done repeatedly for the guidance of an autonomous vehicle. We examine how to formulate some path planning problems precisely, and we report algorithms to solve certain special cases.

Details DOI