CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Randomized adaptive test cover

Peter Damaschke (Institutionen för data- och informationsteknik, Datavetenskap, Algoritmer (Chalmers))
Lecture Notes in Computer Science: 9th International Conference on Algorithms and Complexity CIAC 2015 (0302-9743). Vol. 9079 (2015), p. 182-193.
[Konferensbidrag, refereegranskat]

In a general combinatorial search problem with binary tests we are given a set of elements and a hypergraph of possible tests, and the goal is to find an unknown target element using a minimum number of tests. We explore the expected test number of randomized strategies. We obtain several general results on the ratio of the expected and worst-case deterministic test number, as well as complexity results for hypergraphs of small rank, and we state some open problems.

Nyckelord: combinatorial search, randomization, game theory, LP duality, fractional graph theory



Denna post skapades 2015-06-10. Senast ändrad 2015-10-29.
CPL Pubid: 218177

 

Läs direkt!


Länk till annan sajt (kan kräva inloggning)