De Adwords och Online Bipartite Matching problem har haft en förnyad uppmärksamhet under det senaste årtiondet på grund av deras anslutning till Internet-reklam. Vårt samhälle har bland annat bidragit med nya modeller (särskilt stokastiska) och utvidgningar till de klassiska formuleringarna för att ta itu med de frågor som uppstår till följd av praktiska behov. I detta dokument föreslår vi en ny generalisering baserad på matroider och visar att många av de tidigare resultaten sträcker sig till denna mer allmänna inställning. På grund av matroidernas rika strukturer och uttryckskraft är vår nya miljö potentiellt intressant både i teorin och i praktiken. I den klassiska versionen av problemet, den offline sidan av en bipartite graf är känd initialt medan hörn från online-sidan anländer en i taget tillsammans med sina incident kanter. Målet är att upprätthålla en anständig ungefärlig matchning från vilken ingen kant kan tas bort. Vår generalisering, som kallas Matroid Online Bipartite Matching, kräver dessutom att uppsättningen matchade offline hörn vara oberoende i en given matris. I synnerhet, fallet med partition matriser motsvarar det naturliga scenariot där varje annonsör hanterar flera annonser med en fast total budget. Våra algoritmer uppnår samma prestanda som den klassiska versionen av de problem som övervägs, vilka ofta är de bästa möjliga. Vi presenterar 1 − 1/e-kompetitiva algoritmer för Matroid Online Bipartite Matchning under det lilla bud antagandet, samt en 1 − 1/e-kompetitiv algoritm för Matroid Online Bipartite Matchning i den slumpmässiga ankomstmodellen. En viktig teknisk ingrediens i våra resultat är en noggrant utformad primal-dual vattenfyllning förfarande som rymmer för matroid begränsningar. Detta är inspirerat av utvidgningen av vårt senaste avgiftssystem för Online Bipartite Vertex Cover. Slutligen, med tanke på att endast ett fåtal problem på nätet undersöktes på ett submodulärt sätt, kan de tekniker som införs i detta dokument för att ta itu med submodulalitet i online-miljön vara av oberoende intresse.
REF introducerade Matroid Online Bipartite Matching modell, där uppsättningen av alla matchade offline-agenter krävs för att vara oberoende i en given matroid.
Matroid Online Bipartite Matching and Vertex Cover
{'venue': "EC '16", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}