Gender-aware facility location in multi-gender world. (English) Zbl 1489.68372
Ito, Hiro (ed.) et al., 9th international conference on fun with algorithms, FUN 2018, June 13–15, 2018, La Maddalena Island, Italy. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 100, Article 28, 16 p. (2018).
Summary: This interdisciplinary (GS and CS) paper starts from considering the problem of locating restrooms or locker rooms in a privacy-preserving way, i.e., so that while following the path to one’s room, one cannot peek into another room; the rooms are meant for a multitude of genders, one room per gender. We then proceed to showing that gender inequality (non-uniform treatment of genders by genders) makes the room placement hard. Finally, we delve into specifics of gender definition and consider locating facilities for the genders in a “perfect” way, i.e., so that navigating to the facilities involves only quick binary decisions; on the way, we indicate that there is room for interpretation the facilities under consideration (we outline several possibilities, depending on the application).
For the entire collection see [Zbl 1390.68022].
For the entire collection see [Zbl 1390.68022].
MSC:
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
| 68R10 | Graph theory (including graph drawing) in computer science |
| 90B80 | Discrete location and assignment |
Software:
FPsolveReferences:
| [1] | Srinivasa Arikati and C. Rangan. An efficient algorithm for finding a two-pair, and its applications. {\it Discrete Applied Mathematics}, 31(1):71-74, 1991. · Zbl 0748.05085 |
| [2] | Svante Carlsson, Håkan Jonsson, and Bengt J. Nilsson. Finding the shortest watchman route in a simple polygon. {\it Discrete & Computational Geometry}, 22(3):377-402, 1999. doi: 10.1007/PL00009467. · Zbl 0939.68136 |
| [3] | Thomas Cormen, Charles Leiserson, Ronald Rivest, and Clifford Stein. {\it Introduction to} {\it Algorithms}. The MIT Press, 3rd edition, 2009. · Zbl 1187.68679 |
| [4] | Sandip Das, M Sen, AB Roy, and Douglas B West. Interval digraphs. {\it J. Graph Theory}, 13(2):189-202, 1989. · Zbl 0671.05039 |
| [5] | Donna Dean. Changing ones: 3rd & 4th genders in native America. {\it Women and Military}, 18(2):54-54, 2000. |
| [6] | Moshe Dror, Alon Efrat, Anna Lubiw, and Joseph Mitchell. Touring a sequence of polygons. In Lawrence L. Larmore and Michel X. Goemans, editors, {\it SToC’03}, pages 473-482. ACM, 2003. · Zbl 1192.68354 |
| [7] | Adrian Dumitrescu and Csaba D. Tóth. Watchman tours for polygons with holes. {\it Comput.} {\it Geom.}, 45(7):326-333, 2012. doi:10.1016/j.comgeo.2012.02.001. · Zbl 1239.65016 |
| [8] | Stephan Eidenbenz. Inapproximability of finding maximum hidden sets on polygons and terrains. {\it CGTA}, 21(3):139-153, 2002. · Zbl 0998.68190 |
| [9] | Javier Esparza, Michael Luttenberger, and Maximilian Schlund. Fpsolve: A generic solver for fixpoint equations over semirings. {\it Intl J Foundations of Computer Science}, 26(07):805- 825, 2015. · Zbl 1330.68353 |
| [10] | European Commission. Gendered Innovations. |
| [11] | Michael R. Garey and David S. Johnson. {\it Computers and Intractability}. Freeman & Co., New York, NY, USA, 1979. · Zbl 0411.68039 |
| [12] | Subir Ghosh. {\it Visibility Algorithms in the Plane}. Cambridge University Press, New York, NY, USA, 2007. · Zbl 1149.68076 |
| [13] | J.E. Goodman and J. O’Rourke, editors. {\it Handbook of Discrete and Computational Geo-} {\it metry}. Discrete Mathematics and Its Applications. Taylor & Francis, 2nd edition, 2004. · Zbl 1056.52001 |
| [14] | Sharyn Graham. Sulawesi’s fifth gender. {\it Inside Indonesia}, 66, 2001. |
| [15] | Martin Grötschel, László Lovász, and Alexander Schrijver. {\it Combinatorial optimization}, volume 2. Springer Science & Business Media, 2012. |
| [16] | Dan Gusfield and Robert Irving. {\it The Stable Marriage Problem: Structure and Algorithms}. MIT Press, Cambridge, MA, USA, 1989. · Zbl 0703.68046 |
| [17] | Vi Hart. On Gender, 2015. |
| [18] | Ryan Hayward, Chính Hoàng, and Frédéric Maffray.Optimizing weakly triangulated graphs. {\it Graphs and Combinatorics}, 5(1):339-349, Dec 1989. · Zbl 0679.68082 |
| [19] | Ryan Hayward, Jeremy Spinrad, and R. Sritharan. Weakly chordal graph algorithms via handles. In {\it SODA’00}, pages 42-49, Philadelphia, PA, USA, 2000. Society for Industrial and Applied Mathematics. · Zbl 0956.68104 |
| [20] | Ryan B Hayward. Weakly triangulated graphs. {\it J Comb Theory, Series B}, 39(3):200-208, 1985. · Zbl 0551.05055 |
| [21] | Aaron Homer. Man Uses Women’s Locker Room At Seattle Pool, Says It’s Legal Because Of Anti-Transgender Discrimination Laws, 2016. |
| [22] | M Kay Martin and Barbara Voorhies. {\it Female of the Species}. Columbia University Press, 1975. |
| [23] | J. Mitchell, G. Rote, and G. Woeginger. Minimum-link paths among obstacles. {\it Alg-ca’92}, 8(1):431-459, 1992. · Zbl 0788.68144 |
| [24] | Joseph Mitchell. Approximating watchman routes. In Sanjeev Khanna, editor, {\it Proc. 24th} {\it Annual ACM-SIAM Symp. on Discrete Algorithms, SODA’13, New Orleans, Louisiana,} {\it USA}, pages 844-855. SIAM, 2013. · Zbl 1422.68254 |
| [25] | Joseph S. B. Mitchell, Valentin Polishchuk, and Mikko Sysikaski. Minimum-link paths revisited. {\it Comput. Geom.}, 47(6):651-667, 2014. doi:10.1016/j.comgeo.2013.12.005. · Zbl 1290.65016 |
| [26] | Cynthia J Novack. Ballet, gender and cultural power. In {\it Dance, gender and culture}, pages 34-48. Springer, 1993. |
| [27] | Joseph O’Rourke.{\it Art Gallery Theorems and Algorithms}.The International Series of Monographs on Computer Science. Oxford University Press, New York, NY, 1987. · Zbl 0653.52001 |
| [28] | :15 |
| [29] | :16 |
| [30] | Eli Packer.Computing multiple watchman routes.In Catherine C. McGeoch, editor, {\it SEA’08}, volume 5038 of {\it Lecture Notes in Computer Science}, pages 114-128. Springer, 2008. |
| [31] | :14 |
| [32] | Erich Prisner. A characterization of interval catch digraphs. {\it Discrete Math}, 73(3):285-289, 1989. · Zbl 0669.05038 |
| [33] | Erich Prisner. Algorithms for interval catch digraphs. {\it Discrete Appl Math}, 51(1-2):147-157, 1994. · Zbl 0810.68104 |
| [34] | Arvind Raghunathan. Algorithms for weakly triangulated graphs, 1989. Tech Rep, UC Berkeley. URL: http://www2.eecs.berkeley.edu/Pubs/TechRpts/1989/5196.html. |
| [35] | Londa Schiebinger. Gendered Innovations, 2013. |
| [36] | T Shermer. Hiding people in polygons. {\it Computing}, 42(2):109-131, 1989. · Zbl 0675.68070 |
| [37] | Jeremy P. Spinrad and R. Sritharan. Algorithms for weakly triangulated graphs. {\it Discrete} {\it Applied Mathematics}, 59(2):181-191, 1995. doi:10.1016/0166-218X(93)E0161-Q. · Zbl 0827.68084 |
| [38] | Stanford University. Gendered Innovations. |
| [39] | Steven H Strogatz. Love affairs and differential equations. {\it Mathematics Magazine}, 61(1):35, 1988. |
| [40] | Subhash Suri. A linear-time algorithm for minimum link paths inside a simple polygon. {\it Computer Vision, Graphics and Image Processing}, 35(1):99-110, 1986. · Zbl 0624.68101 |
| [41] | Erica Tempesta. Stereotypes are made to be broken!, 2017. |
| [42] | Randolph Trumbach. {\it From 3 sexes to 4 genders in the making of modern culture}. Routledge, 1991. |
| [43] | Peter Walker. Men need lots of energy to lift ballet dancers because women are getting taller, 2017. |
| [44] | Wikipedia contributors. Strahler number, 2017. |
| [45] | Wikipedia contributors. Hall’s marriage theorem, 2018. |
| [46] | Wikipedia contributors. Third gender, 2018. |
| [47] | Yuming Zou and Paul Black. Perfect binary tree. In Vreda Pieterse and Paul E. Black, editors, {\it Dictionary of Algorithms and Data Structures}. National Institute of Standards and Technology, 2008. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
