Selected Publications of Estie Arkin

E.M. Arkin, N. Guttmann-Beck, R. Hassin (2010):
``The (K,k)-Capacitated Spanning Tree Problem''.

Esther M. Arkin, Alon Efrat, Joseph S. B. Mitchell, Srinivasan Ramasubramanian, Valentin Polishchuk, Swaminathan Sankararaman, and Javad Tahen.
"Data Transmission and Base-Station Placement for Optimizing Network Lifetime"
Proc. Sixth ACM SIGACT/SIGMOBILE International Workshop on Foundations of Mobile Computing (DIALM-POMC), Cambridge, MA, September 16, 2010.

Esther M. Arkin, Joseph S. B. Mitchell, and Valentin Polishchuk.
"Maximum Thick Paths in Static and Dynamic Environments",
Proc. 24th Annual ACM Symposium on Computational Geometry, June 2008.

E.M. Arkin, R. Hassin (2007):
``The k-path tree matroid and its applications to survivable network design''.

E.M. Arkin, B. Abrego S. Fernandez-Merchant F. Hurtado M. Kano, J.S.B. Mitchell and J. Urrutia (2004):
``Matching Points with Geometric Objects: Combinatorial Results''

E.M. Arkin, M.A. Bender, E.D. Demaine, S.P. Fekete, J.S.B. Mitchell, S. Sethia (2001), modified (2005):
``Optimal Covering Tours with Turn Costs''.

E.M. Arkin, M.A. Bender, S.P. Fekete, J.S.B. Mitchell, Martin Skutella (2002), modified (2005):
``The Freeze-Tag Problem: How to Wake Up a Swarm of Robot''.

E.M. Arkin, R. Hassin, A. Levin (2004):
``Approximations for minimum and min-max vehicle routing problems''.

E.M. Arkin, R. Hassin, S. Shahar (2002):
``Increasing digraph arc-connectivity by arc addition, reversal and complement''.

E.M. Arkin, R. Hassin (2001), modified (2004):
``A note on orientations of mixed graphs''.

E.M. Arkin, S. Fekete, J.S.B. Mitchell (2000):
``Approximation algorithms for lawnmowing and milling''.

E.M. Arkin, R. Hassin, M. Sviridenko (1999):
``Approximating the Maximum Quadratic Assignment Problem''.

E.M. Arkin, J.S.B. Mitchell, G. Narasimhan (1997):
``Resource-Constrained Geometric Network Optimization''.

E.M. Arkin, R. Hassin (1997):
``On Local Search for Weighted k-set Packing''.
Proc. European Symposium on Algorithms. Graz, Austria, Sep 15-17, 1997.

E.M. Arkin, R. Hassin (1995):
``Graph Partitions with Minimum Degree Constraints''.

E.M. Arkin, R. Hassin, L. Klein (1997):
``Restricted Delivery Problems on a Network''.
Networks (Vol. 29, 1997, pp. 205-216).

E.M. Arkin, Y-J. Chiang, J.S.B. Mitchell, S.S. Skiena, and T-C. Yang (1997):
``On the Maximum Scatter TSP''.
Proc. 8th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 97). New Orleans, LA, January, 1997.

E.M. Arkin, Y-J. Chiang, M. Held, J.S.B. Mitchell, V. Sacristan, S.S. Skiena, and T-C. Yang (1996):
``On Minimum-Area Hulls''.
Proc. European Symposium on Algorithms. Springer-Verlag, LNCS 1136, J. Diaz and M. Serna (eds.), pp. 334--348; Barcelona, Spain, Sep 25-27, 1996.

E.M. Arkin, R. Hassin (1994):
``Minimum Diameter Covering Problems''.
Networks, 36(3) pages 147-155, 2000.

E.M. Arkin, M. Held, C.L. Smith (1995):
``Optimization Problems Related to Zigzag Pocket Machining''. 7th Annual ACM-SIAM Symp. on Discrete Algorithms (SODA'96), Atlanta, GA, USA, Jan 28-30, 1996.

E.M. Arkin, M. Held, J.S.B. Mitchell, S.S. Skiena (1995):
``Recognizing Polygonal Parts from Width Measurements''.
Proc. 7th Canad. Conf. Computat. Geometry, C. Gold, J.-M. Robert (eds.), pp. 199-204; Québec City, Québec, Canada, Aug 10-13, 1995.

E.M. Arkin, M. Held, J.S.B. Mitchell, S.S. Skiena (1994):
``Hamiltonian Triangulations for Fast Rendering''.
Algorithms -- ESA'94, Springer-Verlag, LNCS 855, J. van Leeuwen (ed.), pp. 36-47; Utrecht, The Netherlands, Sep 26-28, 1994.

E.M. Arkin, R. Hassin (1994):
``Approximation algorithms for the geometric covering salesman problem''.
Discrete Applied Math. 55, pp 197-218, 1994.

E.M. Arkin, M.M. Halldorsson, R. Hassin (1993):
``Approximating the tree and tour covers of a graph''.
Information Processing Letters 47, pp 275-282, 1993.

E.M. Arkin, P. Chew, D.P. Huttenlocher, K. Kedem, J.S.B. Mitchell,
An Efficiently Computable Metric for Comparing Polygonal Shapes,
Technical Report TR 89-1007, Department of Computer Science, Cornell University, May 1989. Appears in First ACM-SIAM Symposium on Discrete Algorithms (SODA'90), San Francisco, CA, January 22-24, 1990, pp. 129-137. Full paper appears in: IEEE Trans. on Pattern Analysis and Machine Intelligence, 13 (3), 1991, pp. 209-216.

E.M. Arkin (1988):
``Beautification is Hard''.
Cornell SORIE Technical Report No. 818, September, 1988.

Estie Arkin (