Klassiska problem med sortering och sökning förutsätter en underliggande linjär beställning av objekten som jämförs. I denna uppsats studerar vi en mer allmän miljö, där vissa par av objekt är ojämförliga. Denna generalisering är relevant i tillämpningar relaterade till ranking i sport, college antagningar, eller konferensbidrag. Det har också potentiella tillämpningar i biologi, såsom att jämföra den evolutionära lämpligheten hos olika stammar av bakterier, eller att förstå input-output relationer bland en uppsättning metaboliska reaktioner eller de kausala influenserna bland en uppsättning interagerande gener eller proteiner. Våra resultat förbättrar och utvidgar resultaten från för två decennier sedan av Faigle och Turán, som var de första att överväga några av de problem som behandlas här. En poset definieras som en uppsättning element med en transitiv partiell ordning där vissa elementpar kan vara ojämförbara. Ett mått på komplexiteten hos en poset ges av dess bredd, som är den maximala storleken på en uppsättning ömsesidigt ojämförbara element. Vi anser algoritmer som får information om en poset genom frågor som jämför två element. Vi överväger två komplexa åtgärder: frågekomplexitet, som bara räknar antalet frågor, och total komplexitet, som räknas alla verksamheter. Vi presenterar en algoritm som sorterar en bredd w poset av storlek n och har frågekomplex O(n(w + log n)), som ligger inom en konstant faktor av den informationsteoretiska nedre gränsen. Vi visar också att en variant av Mergesort har frågekomplex O(wn log n w ) och total komplexitet O(w 2 n log n w ). Faigle och Turán har visat att sorteringsproblemet har fråga komplexitet O wn log n w men inte tar itu med den totala compexity av problemet. Två problem relaterade till sortering är problemet med att hitta de minimala elementen i en poset och dess generalisering av att hitta de nedre k "nivåer", kallas k-val problemet. Vi ger effektiva deterministiska och randomiserade algoritmer för att hitta minimala element med O (wn) fråga och total komplexitet. Vi tillhandahåller matchande lägre gränser för frågan komplexitet upp till en faktor 2 och generalisera resultaten till k-valet problemet. Vi härleder också övre gränser på den totala komplexiteten av några andra problem av en liknande smak, såsom att beräkna en linjär förlängning av en poset och beräkna höjder av alla element. Många öppna problem kvarstår, varav det viktigaste är att fastställa den exakta totala komplexiteten i sorteringen, liksom den exakta frågan och den totala komplexiteten i valet av k. Det skulle också vara intressant att hitta effektiva statiska och dynamiska datastrukturer som spelar samma roll för partiella order som högar och binära sökträd spelar för totala order.
En poset definieras som en uppsättning element med en transitiv partiell ordning, där vissa element kan vara ojämförlig REF.
Sorting and Selection in Posets
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}