@inproceedings{BergSJ:ECAI2016, author = {Jeremias Berg and Paul Saikko and Matti J\"arvisalo}, title = {Subsumed Label Elimination for Maximum Satisfiability}, editor= {Gal A. Kaminka and Maria Fox and Paolo Bouquet and Eyke H{\"{u}}llermeier and Virginia Dignum and Frank Dignum and Frank van Harmelen}, pages = {630--638}, year = {2016}, booktitle = {Proceedings of the 22nd European Conference on Artificial Intelligence (ECAI 2016)}, series = {Frontiers in Artificial Intelligence and Applications}, volume = {285}, publisher = {IOS Press}, } Abstract: We propose subsumed label elimination (SLE), a so-called label-based preprocessing technique for the Boolean optimization paradigm of maximum satisfiability (MaxSAT). We formally show that SLE is orthogonal to previously proposed SAT-based preprocessing techniques for MaxSAT in that it can simplify the underlying minimal unsatisfiable core structure of MaxSAT instances. We also formally show that SLE can considerably reduce the number of internal SAT solver calls within modern core-guided MaxSAT solvers. Empirically, we show that combining SLE with SAT-based preprocessing improves the performance of various state-of-the-art MaxSAT solvers on standard industrial weighted partial MaxSAT benchmarks.