I Matroid Secretary Problem, introducerades av Babaioff et al. [5], elementen i en given matris presenteras för en online-algoritm i slumpmässig ordning. När ett element avslöjas lär sig algoritmen sin vikt och bestämmer om den ska väljas eller inte. Målet är att returnera en maximal vikt oberoende uppsättning av matroid. Det finns olika varianter för detta problem beroende på den information som är känd om vikterna i förväg. I den slumpmässiga tilldelning modell, en dold lista över vikter slumpmässigt tilldelas matroid markuppsättningen, oberoende av den slumpmässiga ordning de avslöjas för algoritmen. Vårt huvudsakliga resultat är den första konstanta algoritmen för denna version av problemet, lösa en öppen fråga om Babaioff et al. Vår algoritm uppnår ett konkurrensförhållande på 2e 2 /(e − 1). Den utnyttjar begreppet huvudpartition av en matroid, dess nedbrytning i jämnt täta minderåriga, och en 2e-konkurrenskraftig algoritm för jämnt täta matroider vi också utvecklar. Vi presenterar också konstanta kompetitiva algoritmer i standardmodellen där vikterna tilldelas motsträvigt, för olika klasser av matroider inklusive cografisk, låg densitet, k-kolumn sparse linjära matroider och fallet när varje element är i en liten kokrets. I samma modell ger vi en ny O(log r)-kompetitiv algoritm för matriser av rank r som endast använder den relativa ordningen av vikterna sett och inte deras faktiska värden, som tidigare behövs.
Till exempel, de delar av marken uppsättningen tilldelas en uppsättning vikter enhetligt på slumpmässiga höna en 5,7187 kompetitiv algoritm är möjlig för någon matroid REF.
Matroid secretary problem in the random assignment model
{'venue': "SODA '11", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}