Rendezvous problem

The rendezvous dilemma is a logical dilemma, typically formulated in this way:

Two people have a date in a park they have never been to before. Arriving separately in the park, they are both surprised to discover that it is a huge area and consequently they cannot find one another. In this situation each person has to choose between waiting in a fixed place in the hope that the other will find them, or else starting to look for the other in the hope that they have chosen to wait somewhere.

If they both choose to wait, they will never meet. If they both choose to walk there are chances that they meet and chances that they do not. If one chooses to wait and the other chooses to walk, then there is a theoretical certainty that they will meet eventually; in practice, though, it may take too long for it to be guaranteed. The question posed, then, is: what strategies should they choose to maximize their probability of meeting?

Examples of this class of problems are known as rendezvous problems. These problems were first introduced informally by Steve Alpern in 1976,[1] and he formalised the continuous version of the problem in 1995.[2] This has led to much recent research in rendezvous search.[3] Even the symmetric rendezvous problem played in n discrete locations (sometimes called the Mozart Cafe Rendezvous Problem)[4] has turned out to be very difficult to solve, and in 1990 Richard Weber and Eddie Anderson conjectured the optimal strategy.[5] In 2012 the conjecture was proved for n = 3 by Richard Weber.[6] This was the first non-trivial symmetric rendezvous search problem to be fully solved. The corresponding asymmetric rendezvous problem has a simple optimal solution: one player stays put and the other player visits a random permutation of the locations.

As well as being problems of theoretical interest, rendezvous problems include real-world problems with applications in the fields of synchronization, operating system design, operations research, and even search and rescue operations planning.

Deterministic rendezvous problem

Main article: Deterministic rendezvous problem

The deterministic rendezvous problem is a variant of the rendezvous problem where the players, or robots, must find each other by following a deterministic sequence of instructions. Although each robot follows the same instruction sequence, a unique label assigned to each robot is used for symmetry breaking.[7]

See also

References

  1. ^ Alpern, Steve (1976), Hide and Seek Games, Seminar, Institut fur Hohere Studien, Wien, 26 July.
  2. ^ Alpern, Steve (1995), "The rendezvous search problem", SIAM Journal on Control and Optimization, 33 (3): 673–683, doi:10.1137/S0363012993249195, MR 1327232
  3. ^ Alpern, Steve; Gal, Shmuel (2003), The Theory of Search Games and Rendezvous, International Series in Operations Research & Management Science, vol. 55, Boston, MA: Kluwer Academic Publishers, ISBN 0-7923-7468-1, MR 2005053.
  4. ^ Alpern, Steve (2011), "Rendezvous search games", in Cochran, James J. (ed.), Wiley Encyclopedia of Operations Research and Management Science, Wiley, doi:10.1002/9780470400531.eorms0720.
  5. ^ Anderson, E. J.; Weber, R. R. (1990), "The rendezvous problem on discrete locations", Journal of Applied Probability, 27 (4): 839–851, doi:10.2307/3214827, JSTOR 3214827, MR 1077533, S2CID 122587972.
  6. ^ Weber, Richard (2012), "Optimal symmetric Rendezvous search on three locations" (PDF), Mathematics of Operations Research, 37 (1): 111–122, doi:10.1287/moor.1110.0528, MR 2891149.
  7. ^ Ta-Shma, Amnon; Zwick, Uri (April 2014). "Deterministic rendezvous, treasure hunts, and strongly universal exploration sequences". ACM Transactions on Algorithms. 10 (3). 12. doi:10.1145/2601068. S2CID 10718957.

Read other articles:

العلاقات الأوغندية الميكرونيسية

العلاقات الأوغندية الميكرونيسية أوغندا ولايات ميكرونيسيا المتحدة   أوغندا   ولايات ميكرونيسيا المتحدة تعديل مصدري - تعديل   العلاقات الأوغندية الميكرونيسية هي العلاقات الثنائية التي تجمع بين أوغندا وولايات ميكرونيسيا المتحدة.[1][2][3][4][5] ...

 

Monty Tiwa

Monty TiwaLahir28 Agustus 1976 (umur 47)Jakarta, IndonesiaAlmamaterUniversitas KansasPekerjaanSutradarapenulisproduserpenyuntingpenyanyikomponisTahun aktif2001—sekarangSuami/istriInovia Witabora Tiwa ​ ​(m. 2004)​Penghargaanlihat daftar Monty Tiwa (lahir 28 Agustus 1976) adalah sutradara, penulis, produser, penyunting, penyanyi, dan komponis Indonesia. Ia meraih penghargaan pertamanya dalam ajang Festival Film Indonesia 2005 kategori Skenario Te...

 

2020 Georgia House of Representatives election

Not to be confused with 2020 United States House of Representatives elections in Georgia. 2020 Georgia House of Representatives election ← 2018 November 3, 2020 2022 → All 180 seats in the Georgia House of Representatives91 seats needed for a majorityTurnout63.01% 9.02 pp   Majority party Minority party   Leader David Ralston Bob Trammell(lost re-election) Party Republican Democratic Leader since January 11, 2010 July 24, 2017 Leader's seat 7th 132nd...

George Conway

American attorney and activist (born 1963) For other people named George Conway, see George Conway (disambiguation). George ConwayConway in 2021BornGeorge Thomas Conway III (1963-09-02) September 2, 1963 (age 60)Boston, Massachusetts, U.S.EducationHarvard University (BA)Yale University (JD)Political partyRepublican (before 2018)Independent (2018–present)Spouse Kellyanne Fitzpatrick ​ ​(m. 2001; sep. 2023)​Children4 George Thomas Conway II...

 

Institut Agama Islam Negeri Kerinci

Institut Agama Islam Negeri KerinciLambang IAIN KerinciJenisPerguruan tinggi Islam negeri di IndonesiaDidirikan1997Lembaga indukKementerian Agama Republik IndonesiaAfiliasiIslamRektorDr. H. Asa'ari, M.Ag.AlamatJl. Kapten Muradi, Koto Lolo, Pesisir Bukit, Kota Sungai Penuh, Jambi, IndonesiaAfiliasiIslamSitus web[1] Institut Agama Islam Negeri Kerinci atau IAIN Kerinci adalah perguruan tinggi Islam negeri di Kabupaten Kerinci, Provinsi Jambi, Indonesia. IAIN Kerinci sebelumnya STAIN Kerinci, di...

 

Brigate Osoppo

Brigate Osoppo-FriuliDescrizione generaleAttiva24 dicembre 1943 - maggio 1945 Nazione Italia TipoBrigate partigiane Motto(FUR) Pai nestris fogolârs(Per i nostri focolari) ComandantiDegni di notaCandido Grassi VerdiManlio Cencig MarioAscanio De Luca AurelioFrancesco De Gregori BollaAldo Bricco Centina SimboliSimbolofazzoletto verdecappello alpino Voci su unità militari presenti su Wikipedia Le Brigate Osoppo-Friuli furono formazioni partigiane autonome fondate presso la sede del Seminar...

2017 Saint Paul mayoral election

2017 Saint Paul mayoral election ← 2013 November 7, 2017 2021 →   Candidate Melvin Carter III Pat Harris Party Democratic (DFL) Democratic (DFL) Popular vote 31,353 15,281 Percentage 50.9% 24.8% Results by city council district Carter:      30–40%      40–50%      50–60%      60–70%Thao:      30–40% Mayor before election Chris ...

 

Adelheid Morath

German cross-country mountain biker This biography of a living person needs additional citations for verification. Please help by adding reliable sources. Contentious material about living persons that is unsourced or poorly sourced must be removed immediately from the article and its talk page, especially if potentially libelous.Find sources: Adelheid Morath – news · newspapers · books · scholar · JSTOR (August 2012) (Learn how and when to remove this...

 

Jorge Jiménez

Questa voce sull'argomento calciatori argentini è solo un abbozzo. Contribuisci a migliorarla secondo le convenzioni di Wikipedia. Segui i suggerimenti del progetto di riferimento. Jorge Jiménez Nazionalità  Argentina Altezza 184 cm Calcio Ruolo Centrocampista Termine carriera 2003 Carriera Squadre di club1 1990-1998 Banfield77 (3)1998-2001 Estudiantes47 (0)2002 Villa Española2 (0)2002-2003 El Porvenir16 (0) Nazionale 1995 Argentina2 (0) Palmarès  Conf...

Billboard Hot 100

Billboard Hot 100Logo du classement.Première édition 4 août 1958Type classement de popularité de chansonsPériodicité Hebdomadaire, annuelCritère Ventes de singles Diffusions en radio Streaming Visionnages sur YouTubeÉditeur BillboardCouverture États-UnisPlus longtemps en tête Lil Nas X featuring Billy Ray Cyrus - Old Town Road (2019) (19 semaines)Site web billboard.com/charts/hot-100modifier - modifier le code - modifier Wikidata Le Billboard Hot 100, établi par le magazine améri...

 

Mobile dating

Relationships(Outline) Types Genetic or adoptive Kinship Family Parent father mother Grandparent Sibling Cousin By marriage Spouse Husband Wife Open marriage Polygamy Polyandry Polygyny Group marriage Mixed-orientation Partner(s) Significant other Boyfriend Girlfriend Cohabitation Same-sex Life partner Friendship (romantic / cross-sex / zone) Intimate and sexual Casual Monogamy Non-monogamy Mutual monogamy Polyamory Polyfidelity Cicisbeo Concubinage Courtesan Mistress Activities Bonding ...

 

Eutaw, Alabama

Eutaw, AlabamaKotaNegara Amerika SerikatNegara bagianlbs Negara bagian AlabamaMontgomery (ibu kota)Topik Sejarah Geografi Orang Pemerintah Gubernur Wakil gubernur Kawasan Metropolitan Tempat wisata Landmark Nasional Bersejarah Wilayah Atlantic Coastal Plain Birmingham District Black Belt Central Alabama Cumberland Plateau Greater Birmingham Gulf Coastal Plain Lower Alabama Mobile Bay North Alabama Northeast Alabama Northwest Alabama Piedmont Ridge and Valley River Region South Alaba...

Поляки в Казахстане

Поляки в Казахстане (пол. Polacy w Kazachstanie, каз. Қазақстандағы поляктар) — одна из национальных диаспор в Казахстане. Часть мировой польской диаспоры, именуемой Полония. В настоящее время в Казахстане живут 35 319 поляков по итогам переписи 2021 года (0,18 % населения республики...

 

J. Marion Sims

American physician and gynecologist (1813-1883) J. Marion SimsJ. Marion Sims, engraving after photograph, ca. 1880BornJames Marion SimsJanuary 25, 1813 (1813-01-25)[1]Lancaster County, South Carolina, U.S.DiedNovember 13, 1883 (1883-11-14) (aged 70)[2]New York City, U.S.Resting placeGreen-Wood Cemetery, Brooklyn, New York, U.S.EducationSouth Carolina CollegeMedical College of CharlestonAlma materJefferson Medical CollegeOccupationSurgeonKnown forvesico...

 

Медаль «10 років незалежності Республіки Казахстан»

Медаль «10 років незалежності Республіки Казахстан»каз. Қазақстан Республикасының тәуелсіздігіне 10 жыл Країна  КазахстанТип МедальСтатус вручається Нагородження Засновано: 27 серпня 2001Нагороджені: Гульшара Абдихалікова d (0)Черговість Старша нагорода Медаль «Шап�...

Constitution of Hawaii

Constitution of the State of HawaiiThe Great Seal of the State of HawaiiOverviewJurisdictionHawaii, United StatesCreatedNovember 7, 1950RatifiedMarch 18, 1959Date effectiveAugust 21, 1959ChambersTwo (bicameral Hawaii State Legislature)ExecutiveGovernor of HawaiiJudiciaryJudiciary of Hawaii The Constitution of the State of Hawaii (Hawaiian: Kumukānāwai o Hawaiʻi), also known as the Hawaii State Constitution,[1] is the fundamental governing document of the U.S. state of Hawaiʻi...

 

Postage stamps and postal history of the Netherlands Antilles

This article is about the postal area called Curaçao or Netherlands Antilles when representing five or six islands. For the current postal region called Curaçao (representing only the island itself), see Postage stamps and postal history of Curaçao. This is a survey of the postage stamps and postal history of the postal areas Netherlands Antilles as well as its predecessor Curaçao. The area consisted of the islands Bonaire, Saba and Sint Eustatius (now part of the Netherlands as postal a...

 

NGC 3895

NGC 3895   الكوكبة الدب الأكبر[1]  رمز الفهرس NGC 3895 (الفهرس العام الجديد)MCG+10-17-080 (فهرس المجرات الموروفولوجي)KPG 303b (Catalogue of isolated pairs of galaxies in the northern hemisphere)UGC 6785 (فهرس أوبسالا العام)PGC 36907 (فهرس المجرات الرئيسية)2MASX J11490400+5925580 (Two Micron All-Sky Survey, Extended source catalogue)Z 292-35 (فهرس المجرات وعنا�...

Jungian interpretation of religion

The Jungian interpretation of religion, pioneered by Carl Jung and advanced by his followers, is an attempt to interpret religion in the light of Jungian psychology. Unlike Sigmund Freud and his followers, Jungians tend to treat religious beliefs and behaviors in a positive light, while offering psychological referents to traditional religious terms such as soul, evil, transcendence, the sacred, and God. Because beliefs do not have to be facts in order for people to hold them, the Jungian in...

 

Asinara

Italian island AsinaraA map showing the location of AsinaraAsinaraLocation of Asinara near SardiniaShow map of SardiniaAsinaraLocation of Asinara within ItalyShow map of ItalyGeographyLocationMediterranean Sea, Stintino Capo Falcone in SardiniaCoordinates41°04′N 8°16′E / 41.067°N 8.267°E / 41.067; 8.267Area51.9 km2 (20.0 sq mi)[1]Length17.4 km (10.81 mi)[1]Width0.29–6.4 km (0.18–3.98 mi)[1]Coastline...