Det är ABSTRACT. Seriation syftar till att rekonstruera en linjär ordning mellan variabler med hjälp av osorterad, parvis likhetsinformation. Det har direkta tillämpningar inom arkeologi och hagelgevär gensekvensering till exempel. Vi skriver seriation som ett optimeringsproblem genom att bevisa ekvivalensen mellan seriation och combinatorial 2-SUM problem på likhetsmatriser (2-SUM är en quadratic minimization problem över permutationer). Seriationsproblemet kan lösas exakt med en spektral algoritm i det ljudlösa fallet och vi härleder flera konvexa avkopplingar för 2-SUM för att förbättra robustheten av seriation lösningar i bullriga inställningar. Dessa konvexa avkopplingar gör det också möjligt för oss att införa strukturella begränsningar på lösningen och därmed lösa halvövervakade seriationsproblem. Vi härleder nya approximationsgränser för några av dessa avkopplingar och presenterar numeriska experiment på arkeologiska data, Markov kedjor och DNA-montering från hagelgevär gensekvensering data.
Nyligen, Fogel et al. REF använde QAP för att lösa problem med seriation och 2-SUM.
Convex Relaxations for Permutation Problems
{'venue': 'NIPS', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}