Vi utformar ett linjärt tid approximationsschema för Gale-Berlekamp Switching Game och generalisera det till en bredare klass av täta sköra minimering problem inklusive den närmaste Codeword Problem (NCP) och unika spel problem. Ytterligare tillämpningar inkluderar bland annat att hitta en begränsad form av matris styvhet och maximal sannolikhet avkodning av en felkorrigeringskod. Som en annan tillämpning av vår metod ger vi de första linjära tid approximation system för korrelation kluster med ett fast antal kluster och dess hierarkiska generalisering. Våra resultat är beroende av en ny teknik för att hantera små objektiva funktionsvärden för optimeringsproblem och kan vara av oberoende intresse.
Två papers [14, REF studera Gale-Berlekamp byta spel och kan ses som en variant av vårt problem över Z 2.
Linear time approximation schemes for the Gale-Berlekamp game and related minimization problems
{'venue': "STOC '09", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}