Partial Optimality in the Linear Ordering Problem

David Stein, Bjoern Andres
Proceedings of the 41st International Conference on Machine Learning, PMLR 235:46514-46529, 2024.

Abstract

The linear ordering problem consists in finding a linear order $<$ on a finite set $A$ so as to minimize the sum of costs associated with pairs of elements $a, b$ for which $a < b$. The problem is NP-hard and APX-hard. We introduce algorithms for solving the problem partially by deciding efficiently for some pairs $(a,b)$ whether $a < b$ is in an optimal solution. To do so, we construct maps from the feasible set of orders to itself and establish efficiently testable conditions on the cost function of the problem for which these maps are improving. We examine the effectiveness and efficiency of these conditions and algorithms empirically, on two data sets.

Cite this Paper

BibTeX
@InProceedings{pmlr-v235-stein24a, title = {Partial Optimality in the Linear Ordering Problem}, author = {Stein, David and Andres, Bjoern}, booktitle = {Proceedings of the 41st International Conference on Machine Learning}, pages = {46514--46529}, year = {2024}, editor = {Salakhutdinov, Ruslan and Kolter, Zico and Heller, Katherine and Weller, Adrian and Oliver, Nuria and Scarlett, Jonathan and Berkenkamp, Felix}, volume = {235}, series = {Proceedings of Machine Learning Research}, month = {21--27 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v235/main/assets/stein24a/stein24a.pdf}, url = {https://proceedings.mlr.press/v235/stein24a.html}, abstract = {The linear ordering problem consists in finding a linear order $<$ on a finite set $A$ so as to minimize the sum of costs associated with pairs of elements $a, b$ for which $a < b$. The problem is NP-hard and APX-hard. We introduce algorithms for solving the problem partially by deciding efficiently for some pairs $(a,b)$ whether $a < b$ is in an optimal solution. To do so, we construct maps from the feasible set of orders to itself and establish efficiently testable conditions on the cost function of the problem for which these maps are improving. We examine the effectiveness and efficiency of these conditions and algorithms empirically, on two data sets.} }
Endnote
%0 Conference Paper %T Partial Optimality in the Linear Ordering Problem %A David Stein %A Bjoern Andres %B Proceedings of the 41st International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2024 %E Ruslan Salakhutdinov %E Zico Kolter %E Katherine Heller %E Adrian Weller %E Nuria Oliver %E Jonathan Scarlett %E Felix Berkenkamp %F pmlr-v235-stein24a %I PMLR %P 46514--46529 %U https://proceedings.mlr.press/v235/stein24a.html %V 235 %X The linear ordering problem consists in finding a linear order $<$ on a finite set $A$ so as to minimize the sum of costs associated with pairs of elements $a, b$ for which $a < b$. The problem is NP-hard and APX-hard. We introduce algorithms for solving the problem partially by deciding efficiently for some pairs $(a,b)$ whether $a < b$ is in an optimal solution. To do so, we construct maps from the feasible set of orders to itself and establish efficiently testable conditions on the cost function of the problem for which these maps are improving. We examine the effectiveness and efficiency of these conditions and algorithms empirically, on two data sets.
APA
Stein, D. & Andres, B.. (2024). Partial Optimality in the Linear Ordering Problem. Proceedings of the 41st International Conference on Machine Learning, in Proceedings of Machine Learning Research 235:46514-46529 Available from https://proceedings.mlr.press/v235/stein24a.html.

Related Material