Eftersom ett system (V, S), V = {1,.., n} och S = {S1,. ., Sm}, den minsta avvikelse problem är att hitta en 2-färg X : V → {−1, +1}, sådan att varje uppsättning är färgad så jämnt som möjligt, dvs.. hitta X för att minimera max j till [m] i.S j X (i). I den här artikeln ger vi de första polynomiska tidsalgoritmerna för diskrepansminimering som uppnår gränser liknande dem som är kända existentiellt med hjälp av den så kallade Entropy Method. Vi ger också ett första ungefärligt resultat för diskrepanser. Speciellt ger vi effektiva randomiserade algoritmer till: 1) Konstruera en O(n 1/2 ) diskrepans färgning för allmänna uppsättningar system när m = O(n), matchar den berömda resultatet av Spencer [17] upp till O(1) faktorer. Mer allmänt, för m ≥ n, får vi en diskrepans av O(n 1/2 log(2m/n)). 2) Skapa en färg med avvikelse O(t 1/2 log n), om varje element ligger i som mest t-uppsättningar. Detta motsvarar det (icke-konstruktiva) resultatet av srinivasan [19]. där λ är den ärftliga avvikelsen i det inställda systemet. Huvudidén i våra algoritmer är att producera en färg över tid genom att låta färgen på elementen utföra en slumpmässig promenad (med små steg) från 0 tills de når ±1. Vid varje steg slumpmässiga humle för olika element korreleras med en lösning till ett semidefinit program, där detta program bestäms av nuvarande tillstånd och entropimetoden. Index Terms-Diskrepacy Theory, Constructive Algorithms. Låta (V, S) vara ett set-system, där V = {1,.., n} är elementen och S = {S 1,. ., S m } är en samling av undergrupper av V. Med tanke på en {‐1, +1} färgning X av element i V, låt X (S j ) = i-Sj X (i) betecknar diskrepansen av X för uppsättning S. Skillnaden i samlingen S definieras som disk(S) = min X max j-[m] X (S j )...., S m } är en samling av undergrupper av V. Att förstå diskrepansen i olika uppsättningssystem har varit ett stort forskningsområde både inom matematik och datavetenskap, och denna studie har avslöjat fascinerande kopplingar till olika områden av matematik. Diskretion har också en rad tillämpningar till flera ämnen inom datavetenskap såsom probabilistiska och approximativa algoritmer, beräkningsgeometri, numerisk integration, derandomisering, kommunikations komplexitet, maskininlärning, optimering och så vidare. Vi ska inte försöka beskriva dessa anslutningar och tillämpningar här, utan hänvisa läsaren till [6], [9], [12]. Vad är skillnaden mellan ett godtyckligt system med n-element och m-uppsättningar?
Bansal REF visade att en semidefinit avkoppling kan användas för att utforma en pseudo-tillnärmning algoritm för ärftlig diskrepans.
Constructive Algorithms for Discrepancy Minimization
{'venue': '2010 IEEE 51st Annual Symposium on Foundations of Computer Science', 'journal': '2010 IEEE 51st Annual Symposium on Foundations of Computer Science', 'mag_field_of_study': ['Mathematics', 'Computer Science']}