Esther M. Arkin

According to our database, Esther M. Arkin authored at least 103 papers between 1986 and 2023.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2023

Fair subgraph selection for contagion containment (Brief Announcement).

Esther M. Arkin, Rezaul Alam Chowdhury, Mayank Goswami, Jason Huang, Joseph S. B. Mitchell, Valentin Polishchuk, Rakesh Ravindran

Proceedings of the XII Latin-American Algorithms, Graphs and Optimization Symposium, 2023

2021

Universal Reconfiguration of Facet-Connected Modular Robots by Pivots: The O(1) Musketeers.

Hugo A. Akitaya, Esther M. Arkin, Mirela Damian, Erik D. Demaine, Vida Dujmovic, Robin Y. Flatland, Matias Korman, Belén Palop, Irene Parada, André van Renssen, Vera Sacristán

Algorithmica, 2021

2020

Computing β-Stretch Paths in Drawings of Graphs.

Esther M. Arkin, Faryad Darabi Sahneh, Alon Efrat, Fabian Frank, Radoslav Fulek, Stephen G. Kobourov, Joseph S. B. Mitchell

Proceedings of the 17th Scandinavian Symposium and Workshops on Algorithm Theory, 2020

Data inference from encrypted databases: a multi-dimensional order-preserving matching approach.

Yanjun Pan, Alon Efrat, Ming Li, Boyang Wang, Hanyu Quan, Joseph S. B. Mitchell, Jie Gao, Esther M. Arkin

Proceedings of the Mobihoc '20: The Twenty-first ACM International Symposium on Theory, 2020

Cutting Polygons into Small Pieces with Chords: Laser-Based Localization.

Esther M. Arkin, Rathish Das, Jie Gao, Mayank Goswami, Joseph S. B. Mitchell, Valentin Polishchuk, Csaba D. Tóth

Proceedings of the 28th Annual European Symposium on Algorithms, 2020

2019

Locating battery charging stations to facilitate almost shortest paths.

Esther M. Arkin, Paz Carmi, Matthew J. Katz, Joseph S. B. Mitchell, Michael Segal

Discret. Appl. Math., 2019

Data Races and the Discrete Resource-time Tradeoff Problem with Resource Reuse over Paths.

Rathish Das, Shih-Yu Tsai, Sharmila Duppala, Jayson Lynch, Esther M. Arkin, Rezaul Chowdhury, Joseph S. B. Mitchell, Steven Skiena

Proceedings of the 31st ACM on Symposium on Parallelism in Algorithms and Architectures, 2019

2018

Selecting and covering colored points.

Esther M. Arkin, Aritra Banik, Paz Carmi, Gui Citovsky, Matthew J. Katz, Joseph S. B. Mitchell, Marina Simakov

Discret. Appl. Math., 2018

2017

Secure communication through jammers jointly optimized in geography and time.

Yair Allouche, Esther M. Arkin, Yuval Cassuto, Alon Efrat, Guy Grebla, Joseph S. B. Mitchell, Swaminathan Sankararaman, Michael Segal

Pervasive Mob. Comput., 2017

Mobile r-gather: Distributed and Geographic Clustering for Location Anonymity.

Jiemin Zeng, Gaurish Telang, Matthew P. Johnson, Rik Sarkar, Jie Gao, Esther M. Arkin, Joseph S. B. Mitchell

Proceedings of the 18th ACM International Symposium on Mobile Ad Hoc Networking and Computing, 2017

Network Optimization on Partitioned Pairs of Points.

Esther M. Arkin, Aritra Banik, Paz Carmi, Gui Citovsky, Su Jia, Matthew J. Katz, Tyler Mayer, Joseph S. B. Mitchell

Proceedings of the 28th International Symposium on Algorithms and Computation, 2017

Joint sensing duty cycle scheduling for heterogeneous coverage guarantee.

Kin Sum Liu, Tyler Mayer, Hao-Tsung Yang, Esther M. Arkin, Jie Gao, Mayank Goswami, Matthew P. Johnson, Nirman Kumar, Shan Lin

Proceedings of the 2017 IEEE Conference on Computer Communications, 2017

2016

Shortest path to a segment and quickest visibility queries.

Valentin Polishchuk, Esther M. Arkin, Alon Efrat, Christian Knauer, Joseph S. B. Mitchell, Günter Rote, Lena Schlipf, Topi Talvitie

J. Comput. Geom., 2016

The Shortest Separating Cycle Problem.

Esther M. Arkin, Jie Gao, Adam Hesterberg, Joseph S. B. Mitchell, Jiemin Zeng

Proceedings of the Approximation and Online Algorithms - 14th International Workshop, 2016

2015

Bichromatic 2-center of pairs of points.

Esther M. Arkin, José Miguel Díaz-Báñez, Ferran Hurtado, Piyush Kumar, Joseph S. B. Mitchell, Belén Palop, Pablo Pérez-Lantero, Maria Saumell, Rodrigo I. Silveira

Comput. Geom., 2015

Probabilistic bounds on the length of a longest edge in Delaunay graphs of random points in d-dimensions.

Esther M. Arkin, Antonio Fernández Anta, Joseph S. B. Mitchell, Miguel A. Mosteiro

Comput. Geom., 2015

Optimizing Read Reversals for Sequence Compression - (Extended Abstract).

Zhong Sichen, Lu Zhao, Yan Liang, Mohammadzaman Zamani, Rob Patro, Rezaul Chowdhury, Esther M. Arkin, Joseph S. B. Mitchell, Steven Skiena

Proceedings of the Algorithms in Bioinformatics - 15th International Workshop, 2015

Choice Is Hard.

Esther M. Arkin, Aritra Banik, Paz Carmi, Gui Citovsky, Matthew J. Katz, Joseph S. B. Mitchell, Marina Simakov

Proceedings of the Algorithms and Computation - 26th International Symposium, 2015

Optimal placement of protective jammers for securing wireless transmissions in a geographic domain.

Esther M. Arkin, Yuval Cassuto, Alon Efrat, Guy Grebla, Joseph S. B. Mitchell, Swaminathan Sankararaman, Michael Segal

Proceedings of the 14th International Conference on Information Processing in Sensor Networks, 2015

Conflict-free Covering.

Esther M. Arkin, Aritra Banik, Paz Carmi, Gui Citovsky, Matthew J. Katz, Joseph S. B. Mitchell, Marina Simakov

Proceedings of the 27th Canadian Conference on Computational Geometry, 2015

2014

Scandinavian Thins on Top of Cake: New and Improved Algorithms for Stacking and Packing.

Helmut Alt, Esther M. Arkin, Alon Efrat, George Hart, Ferran Hurtado, Irina Kostitsyna, Alexander Kröller, Joseph S. B. Mitchell, Valentin Polishchuk

Theory Comput. Syst., 2014

Convex transversals.

Esther M. Arkin, Claudia Dieckmann, Christian Knauer, Joseph S. B. Mitchell, Valentin Polishchuk, Lena Schlipf, Shang Yang

Comput. Geom., 2014

Data transmission and base-station placement for optimizing the lifetime of wireless sensor networks.

Esther M. Arkin, Alon Efrat, Joseph S. B. Mitchell, Valentin Polishchuk, Srinivasan Ramasubramanian, Swaminathan Sankararaman, Javad Taheri

Ad Hoc Networks, 2014

2012

Separability of Point Sets by k-Level Linear Classification Trees.

Esther M. Arkin, Delia Garijo, Alberto Márquez, Joseph S. B. Mitchell, Carlos Seara

Int. J. Comput. Geom. Appl., 2012

The (K, k)-capacitated spanning tree problem.

Esther M. Arkin, Nili Guttmann-Beck, Refael Hassin

Discret. Optim., 2012

Scandinavian Thins on Top of Cake: On the Smallest One-Size-Fits-All Box.

Esther M. Arkin, Alon Efrat, George Hart, Irina Kostitsyna, Alexander Kröller, Joseph S. B. Mitchell, Valentin Polishchuk

Proceedings of the Fun with Algorithms - 6th International Conference, 2012

2011

The snowblower problem.

Esther M. Arkin, Michael A. Bender, Joseph S. B. Mitchell, Valentin Polishchuk

Comput. Geom., 2011

2010

Maximum thick paths in static and dynamic environments.

Esther M. Arkin, Joseph S. B. Mitchell, Valentin Polishchuk

Comput. Geom., 2010

Data transmission and base-station placement for optimizing network lifetime.

Esther M. Arkin, Valentin Polishchuk, Alon Efrat, Srinivasan Ramasubramanian, Javad Taheri, Joseph S. B. Mitchell, Swaminathan Sankararaman

Proceedings of the DIALM-POMC Joint Workshop on Foundations of Mobile Computing, 2010

The (<i>K</i>, <i>k</i>)-Capacitated Spanning Tree Problem.

Esther M. Arkin, Nili Guttmann-Beck, Refael Hassin

Proceedings of the Algorithmic Aspects in Information and Management, 2010

2009

Geometric stable roommates.

Esther M. Arkin, Sang Won Bae, Alon Efrat, Kazuya Okamoto, Joseph S. B. Mitchell, Valentin Polishchuk

Inf. Process. Lett., 2009

Matching Points with Squares.

Bernardo M. Ábrego, Esther M. Arkin, Silvia Fernández-Merchant, Ferran Hurtado, Mikio Kano, Joseph S. B. Mitchell, Jorge Urrutia

Discret. Comput. Geom., 2009

Not being (super)thin or solid is hard: A study of grid Hamiltonicity.

Esther M. Arkin, Sándor P. Fekete, Kamrul Islam, Henk Meijer, Joseph S. B. Mitchell, Yurai Núñez Rodríguez, Valentin Polishchuk, David Rappaport, Henry Xiao

Comput. Geom., 2009

2008

Capturing crossings: Convex hulls of segment and plane intersections.

Esther M. Arkin, Joseph S. B. Mitchell, Jack Snoeyink

Inf. Process. Lett., 2008

The k-path tree matroid and its applications to survivable network design.

Esther M. Arkin, Refael Hassin

Discret. Optim., 2008

The Embroidery Problem.

Esther M. Arkin, George Hart, Joondong Kim, Irina Kostitsyna, Joseph S. B. Mitchell, Girishkumar Sabhnani, Steven Skiena

Proceedings of the 20th Annual Canadian Conference on Computational Geometry, 2008

2007

Two New Classes of Hamiltonian Graphs: (Extended Abstract).

Esther M. Arkin, Joseph S. B. Mitchell, Valentin Polishchuk

Electron. Notes Discret. Math., 2007

2006

Approximations for minimum and min-max vehicle routing problems.

Esther M. Arkin, Refael Hassin, Asaf Levin

J. Algorithms, 2006

Some Lower Bounds on Geometric Separability Problems.

Esther M. Arkin, Ferran Hurtado, Joseph S. B. Mitchell, Carlos Seara, Steven Skiena

Int. J. Comput. Geom. Appl., 2006

Minimum-Cost Coverage of Point Sets by Disks

Esther M. Arkin, Hervé Brönnimann, Jeff Erickson, Sándor P. Fekete, Christian Knauer, Jonathan Lenchner, Joseph S. B. Mitchell, Kim Whittlesey

CoRR, 2006

The Freeze-Tag Problem: How to Wake Up a Swarm ofRobots.

Esther M. Arkin, Michael A. Bender, Sándor P. Fekete, Joseph S. B. Mitchell, Martin Skutella

Algorithmica, 2006

Algorithms for two-box covering.

Esther M. Arkin, Gill Barequet, Joseph S. B. Mitchell

Proceedings of the 22nd ACM Symposium on Computational Geometry, 2006

Minimum-cost coverage of point sets by disks.

Helmut Alt, Esther M. Arkin, Hervé Brönnimann, Jeff Erickson, Sándor P. Fekete, Christian Knauer, Jonathan Lenchner, Joseph S. B. Mitchell, Kim Whittlesey

Proceedings of the 22nd ACM Symposium on Computational Geometry, 2006

Hamiltonian Cycles in Triangular Grids.

Valentin Polishchuk, Esther M. Arkin, Joseph S. B. Mitchell

Proceedings of the 18th Annual Canadian Conference on Computational Geometry, 2006

2005

Optimal Covering Tours with Turn Costs.

Esther M. Arkin, Michael A. Bender, Erik D. Demaine, Sándor P. Fekete, Joseph S. B. Mitchell, Saurabh Sethia

SIAM J. Comput., 2005

2004

Theoretical and experimental analysis of heuristics for the "freeze-tag" robot awakening problem.

Marcelo O. Sztainberg, Esther M. Arkin, Michael A. Bender, Joseph S. B. Mitchell

IEEE Trans. Robotics, 2004

When can you fold a map?

Esther M. Arkin, Michael A. Bender, Erik D. Demaine, Martin L. Demaine, Joseph S. B. Mitchell, Saurabh Sethia, Steven Skiena

Comput. Geom., 2004

Approximations for Maximum Transportation with Permutable Supply Vector and Other Capacitated Star Packing Problems.

Esther M. Arkin, Refael Hassin, Shlomi Rubinstein, Maxim Sviridenko

Algorithmica, 2004

Matching Points with Circles and Squares.

Bernardo M. Ábrego, Esther M. Arkin, Silvia Fernández-Merchant, Ferran Hurtado, Mikio Kano, Joseph S. B. Mitchell, Jorge Urrutia

Proceedings of the Discrete and Computational Geometry, Japanese Conference, 2004

2003

Minimum-link watchman tours.

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

Inf. Process. Lett., 2003

The Lazy Bureaucrat scheduling problem.

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

Inf. Comput., 2003

An algorithmic study of manufacturing paperclips and other folded structures.

Esther M. Arkin, Sándor P. Fekete, Joseph S. B. Mitchell

Comput. Geom., 2003

Improved approximation algorithms for the freeze-tag problem.

Esther M. Arkin, Michael A. Bender, Dongdong Ge

Proceedings of the SPAA 2003: Proceedings of the Fifteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2003

Online dispersion algorithms for swarms of robots.

Tien-Ruey Hsiang, Esther M. Arkin, Michael A. Bender, Sándor P. Fekete, Joseph S. B. Mitchell

Proceedings of the 19th ACM Symposium on Computational Geometry, 2003

2002

Increasing digraph arc-connectivity by arc addition, reversal and complement.

Esther M. Arkin, Refael Hassin, Shimon Shahar

Discret. Appl. Math., 2002

A note on orientations of mixed graphs.

Esther M. Arkin, Refael Hassin

Discret. Appl. Math., 2002

Algorithms for Rapidly Dispersing Robot Swarms in Unknown Environments.

Tien-Ruey Hsiang, Esther M. Arkin, Michael A. Bender, Sándor P. Fekete, Joseph S. B. Mitchell

Proceedings of the Algorithmic Foundations of Robotics V, 2002

Analysis of Heuristics for the Freeze-Tag Problem.

Marcelo O. Sztainberg, Esther M. Arkin, Michael A. Bender, Joseph S. B. Mitchell

Proceedings of the Algorithm Theory, 2002

Approximations for Maximum Transportation Problem with Permutable Supply Vector and Other Capacitated Star Packing Problems.

Esther M. Arkin, Refael Hassin, Shlomi Rubinstein, Maxim Sviridenko

Proceedings of the Algorithm Theory, 2002

The freeze-tag problem: how to wake up a swarm of robots.

Esther M. Arkin, Michael A. Bender, Sándor P. Fekete, Joseph S. B. Mitchell, Martin Skutella

Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002

Processor Allocation on Cplant: Achieving General Processor Locality Using One-Dimensional Allocation Strategies.

Vitus J. Leung, Esther M. Arkin, Michael A. Bender, David P. Bunde, Jeanette Johnston, Alok Lal, Joseph S. B. Mitchell, Cynthia A. Phillips, Steven S. Seiden

Proceedings of the 2002 IEEE International Conference on Cluster Computing (CLUSTER 2002), 2002

2001

Approximating the maximum quadratic assignment problem.

Esther M. Arkin, Refael Hassin, Maxim Sviridenko

Inf. Process. Lett., 2001

On the Reflexivity of Point Sets.

Esther M. Arkin, Sándor P. Fekete, Ferran Hurtado, Joseph S. B. Mitchell, Marc Noy, Vera Sacristán, Saurabh Sethia

Proceedings of the Algorithms and Data Structures, 7th International Workshop, 2001

2000

Minimum-diameter covering problems.

Esther M. Arkin, Refael Hassin

Networks, 2000

Approximation algorithms for lawn mowing and milling.

Esther M. Arkin, Sándor P. Fekete, Joseph S. B. Mitchell

Comput. Geom., 2000

Letter to the editor: an algorithm for reducing tool retractions in zigzag pocket machining.

Martin Held, Esther M. Arkin

Comput. Aided Des., 2000

Optimization Problems Related to Zigzag Pocket Machining.

Esther M. Arkin, Martin Held, Christopher L. Smith

Algorithmica, 2000

Approximating the maximum quadratic assignment problem.

Esther M. Arkin, Refael Hassin

Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2000

Some Separability Problems in the Plane.

Esther M. Arkin, Ferran Hurtado, Joseph S. B. Mitchell, Carlos Seara, Steven Skiena

EuroCG, 2000

1999

On the Maximum Scatter Traveling Salesperson Problem.

Esther M. Arkin, Yi-Jen Chiang, Joseph S. B. Mitchell, Steven Skiena, Tae-Cheon Yang

SIAM J. Comput., 1999

1998

On Local Search for Weighted <i>k</i>-Set Packing.

Esther M. Arkin, Refael Hassin

Math. Oper. Res., 1998

Decision trees for geometric models.

Esther M. Arkin, Henk Meijer, Joseph S. B. Mitchell, David Rappaport, Steven Skiena

Int. J. Comput. Geom. Appl., 1998

Graph partitions with minimum degree constraints.

Esther M. Arkin, Refael Hassin

Discret. Math., 1998

Recognizing polygonal parts from width measurements.

Esther M. Arkin, Martin Held, Joseph S. B. Mitchell, Steven Skiena

Comput. Geom., 1998

On Minimum-Area Hulls.

Esther M. Arkin, Yi-Jen Chiang, Martin Held, Joseph S. B. Mitchell, Vera Sacristán, Steven Skiena, Tae-Heng Yang

Algorithmica, 1998

Resource-Constrained Geometric Network Optimization.

Esther M. Arkin, Joseph S. B. Mitchell, Giri Narasimhan

Proceedings of the Fourteenth Annual Symposium on Computational Geometry, 1998

1997

Restricted delivery problems on a network.

Esther M. Arkin, Refael Hassin, Limor Klein

Networks, 1997

Guest Editors' Foreword.

Esther M. Arkin, Joseph S. B. Mitchell, Steven Skiena

Int. J. Comput. Geom. Appl., 1997

Testing Simple Polygons.

Esther M. Arkin, Patrice Belleville, Joseph S. B. Mitchell, David M. Mount, Kathleen Romanik, Steven Salzberg, Diane L. Souvaine

Comput. Geom., 1997

On the Maximum Scatter TSP (Extended Abstract).

Esther M. Arkin, Yi-Jen Chiang, Joseph S. B. Mitchell, Steven Skiena, Tae-Cheon Yang

Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 1997

On Local Search for Weighted k-Set Packing.

Esther M. Arkin, Refael Hassin

Proceedings of the Algorithms, 1997

Geometric Decision Trees for Optical Character Recognition (Extended Abstract).

George N. Sazaklis, Esther M. Arkin, Joseph S. B. Mitchell, Steven Skiena

Proceedings of the Thirteenth Annual Symposium on Computational Geometry, 1997

1996

Hamiltonian triangulations for fast rendering.

Esther M. Arkin, Martin Held, Joseph S. B. Mitchell, Steven Skiena

Vis. Comput., 1996

Optimization Problems Related to Zigzag Pocket Machining (Extended Abstract).

Esther M. Arkin, Martin Held, Christopher L. Smith

Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 1996

On Minimum-Area Hulls (Extended Abstract).

Esther M. Arkin, Yi-Jen Chiang, Martin Held, Joseph S. B. Mitchell, Vera Sacristán, Steven Skiena, Tae-Heng Yang

Proceedings of the Algorithms, 1996

1995

Logarithmic-time link path queries in a simple polygon.

Esther M. Arkin, Joseph S. B. Mitchell, Subhash Suri

Int. J. Comput. Geom. Appl., 1995

Arrangements of Segments that Share Endpoints Single Face Results.

Esther M. Arkin, Dan Halperin, Klara Kedem, Joseph S. B. Mitchell, Nir Naor

Discret. Comput. Geom., 1995

1994

Approximation Algorithms for the Geometric Covering Salesman Problem.

Esther M. Arkin, Refael Hassin

Discret. Appl. Math., 1994

Hamilton Triangulations for Fast Rendering.

Esther M. Arkin, Martin Held, Joseph S. B. Mitchell, Steven Skiena

Proceedings of the Algorithms, 1994

1993

Approximating the Tree and Tour Covers of a Graph.

Esther M. Arkin, Magnús M. Halldórsson, Refael Hassin

Inf. Process. Lett., 1993

Geometric Knapsack Problems.

Esther M. Arkin, Samir Khuller, Joseph S. B. Mitchell

Algorithmica, 1993

Point Probe Decision Trees for Geometric Concept Classes.

Esther M. Arkin, Michael T. Goodrich, Joseph S. B. Mitchell, David M. Mount, Christine D. Piatko, Steven Skiena

Proceedings of the Algorithms and Data Structures, Third Workshop, 1993

The Lawnmower Problem.

Esther M. Arkin, Sándor P. Fekete, Joseph S. B. Mitchell

Proceedings of the 5th Canadian Conference on Computational Geometry, 1993

1992

Matching Points into Pairwise-Disjoint Noise Regions: Combinatorial Bounds and Algorithms.

Esther M. Arkin, Klara Kedem, Joseph S. B. Mitchell, Josef Sprinzak, Michael Werman

INFORMS J. Comput., 1992

Optimal Link Path Queries in a Simple Polygon.

Esther M. Arkin, Joseph S. B. Mitchell, Subhash Suri

Proceedings of the Third Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1992

Computing a Shortest k-Link Path in a Polygon

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

Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, 1992

1991

An Efficiently Computable Metric for Comparing Polygonal Shapes.

Esther M. Arkin, L. Paul Chew, Daniel P. Huttenlocher, Klara Kedem, Joseph S. B. Mitchell

IEEE Trans. Pattern Anal. Mach. Intell., 1991

Modularity of Cycles and Paths in Graphs.

Esther M. Arkin, Christos H. Papadimitriou, Mihalis Yannakakis

J. ACM, 1991

Weighted-Tardiness Scheduling on Parallel Machines with Proportional Weights.

Esther M. Arkin, Robin O. Roundy

Oper. Res., 1991

Matching Points into Noise Regions: Combinatorial Bounds and Algorithms.

Esther M. Arkin, Klara Kedem, Joseph S. B. Mitchell, Josef Sprinzak, Michael Werman

Proceedings of the Second Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1991

1989

On Monotone Paths Among Obstacles with Applications to Planning Assemblies.

Esther M. Arkin, Robert Connelly, Joseph S. B. Mitchell

Proceedings of the Fifth Annual Symposium on Computational Geometry, 1989

1987

Scheduling jobs with fixed start and end times.

Esther M. Arkin, Ellen B. Silverberg

Discret. Appl. Math., 1987

1986

On the Complexity of Circulations.

Esther M. Arkin, Christos H. Papadimitriou

J. Algorithms, 1986