Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2502.14536 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912557161250816 |
|---|---|
| author | Irmai, Jannik Moeller, Maximilian Andres, Bjoern |
| author_facet | Irmai, Jannik Moeller, Maximilian Andres, Bjoern |
| contents | The NP-hard maximum value preordering problem is both a joint relaxation and a hybrid of the clique partition problem (a clustering problem) and the partial ordering problem. Toward approximate solutions and lower bounds, we introduce a linear-time 4-approximation algorithm that constructs a maximum dicut of a subgraph and define local search heuristics. Toward upper bounds, we tighten a linear program relaxation by the class of odd closed walk inequalities that define facets, as we show, of the preorder polytope. We contribute implementations of the algorithms, apply these to the task of jointly clustering and partially ordering the accounts of published social networks, and compare the output and efficiency qualitatively and quantitatively. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_14536 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Algorithms for the preordering problem and their application to the task of jointly clustering and ordering the accounts of a social network Irmai, Jannik Moeller, Maximilian Andres, Bjoern Machine Learning The NP-hard maximum value preordering problem is both a joint relaxation and a hybrid of the clique partition problem (a clustering problem) and the partial ordering problem. Toward approximate solutions and lower bounds, we introduce a linear-time 4-approximation algorithm that constructs a maximum dicut of a subgraph and define local search heuristics. Toward upper bounds, we tighten a linear program relaxation by the class of odd closed walk inequalities that define facets, as we show, of the preorder polytope. We contribute implementations of the algorithms, apply these to the task of jointly clustering and partially ordering the accounts of published social networks, and compare the output and efficiency qualitatively and quantitatively. |
| title | Algorithms for the preordering problem and their application to the task of jointly clustering and ordering the accounts of a social network |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2502.14536 |