I. D. Sanders
ABSTRACT
There are many people who have different size feet and need different sizes of shoes to get shoes that fit well. A static approach to solving the problem could be to get a list of all the people who need shoes and their size requirements, then from that list find groups of people who can cooperate. In a graph theory sense this means creating a directed graph from the input data, finding all of the simple cycles in the graph and then picking the smallest set of cycles such that each node in a cycle in the original graph is in at least one cycle in the final set of cycles.
This paper looks at a more dynamic approach of dealing with the problem. People who need shoes enter the system, by giving their shoe size requirements, and remain in the system until their needs have been satisfied. This approach is represented by an online algorithm which stores all the possible paths in the graph at any stage, checks for cycles when a new person enters the system and updates appropriately in each iteration. The online algorithm can also accommodate "altruism" (where an individual chooses to stay in the system to assist others to buy shoes) and spreading the cost of buying additional pairs of shoes (for example, two people buying three pairs of shoes) in order for individuals to more quickly have their shoe needs satisfied. The three versions of the online algorithm were implemented and tested on synthetic data. The online algorithm generally satisfies the needs of the people entering the system although its performance is sometimes affected by the lack of knowledge of the entire input set.
- S. Albers. Online algorithms: a survey. Mathematical Programming, 97(1-2):3--26, 2003.Google Scholar
Cross Ref
- N. Alon, B. Awerbuch, Y. Azar, N. Buchbinder, and J. S. Naor. The online set cover problem. SIAM Journal of Computing, 39(2):361--370, 2009. Google ScholarDigital Library
- K. Basson. OddShoeFinder.com, 2007. http://oddshoefinder.com/, Last retrieved "31 January 2013".Google Scholar
- G. Divèki and C. Imreh. Online facility location with facility movements. Central European Journal of Operations Research, 19(2):191--200, 2011.Google ScholarCross Ref
- L. Epstein. Online bin packing with cardinality constraints. SIAM Journal of Discrete Mathematics, 20(4):1015--1030, 2006. Google ScholarDigital Library
- D. Fotakis. Online and incremental algorithms for facility location. SIGACT News, 42(1):97--131, Mar. 2011. Google ScholarDigital Library
- E. Grove, M.-Y. Kao, P. Krishnan, and J. S. Vitter. Online perfect matching and mobile computing. In Proceedings of International Workshop on Algorithms and Data Structures, 1995. Google ScholarDigital Library
- D. B. Johnson. Finding all the elementary circuits of a directed graph. SIAM Journal on Computing, 4:77--84, 1975.Google ScholarDigital Library
- H. Liu and J. Wang. A new way to enumerate cycles in graph. In Proceedings of the Advanced International Conference on Telecommunications and International Conference on Internet and Web Applications and Services (AICT/ICIW 2006), 2006. Google ScholarDigital Library
- A. Meyerson. Online facility location. In Foundations of Computer Science, 2001. Proceedings. 42nd IEEE Symposium on, pages 426--431, 2001. Google ScholarDigital Library
- R. Neapolitan and K. Naimipour. Foundations of Algorithms. Jones and Bartlett, Sudbury, MA, 1997. Google ScholarDigital Library
- I. D. Sanders. Cooperating to buy shoes: An application of picking cycles in directed graphs. In Proceedings of the 2013 SAICSIT conference. SAICSIT, 7--9 October 2013. Google ScholarDigital Library
- R. Shah, P. J. Varman, and J. S. Vitter. Online algorithms for prefetching and caching on parallel disks. In Proceedings of the sixteenth annual ACM Symposium on Parallelism in Algorithms and Architectures, SPAA '04, pages 255--264, New York, NY, USA, 2004. ACM. Google ScholarDigital Library
- S. Vassallo and R. Stern. Shoes Without A Partner, 2005. http://www.e-bility.com/disability-news/swapshoes.php, Last retrieved "31 January 2013".Google Scholar
Index Terms
- Cooperating to buy shoes in the real world: online cycle picking in directed graphs
Recommendations
Cooperating to buy shoes: an application of picking cycles in directed graphs
SAICSIT '13: Proceedings of the South African Institute for Computer Scientists and Information Technologists ConferenceIn this paper cycle picking in defined as an optimisation problem where cycles are chosen from a directed graph under the constraint that any node that is in a cycle in the original directed graph must be in at least one of the chosen cycles. This ...
Pace-sync shoes: intuitive walking-pace guidance based on cyclic vibro-tactile stimulation for the foot
We propose a walking guidance method with a sandal-shaped vibration interface and describe two experiments we performed to formulate the design principles of the interface. In the interface, a vibrating motor presents timing information to the foot, and ...
Comments