Recently, while working on a project, I encountered an algorithmic problem that I had been stuck on for quite some time.↵
It would be great to hear ideas about possible approaches (right now, I haven’t even been able to come up with a polynomial-time algorithm) or an idea to show its reduction from some NP-hard problem.↵
↵
↵
Consider a single-voter election where a set of candidates C1, C2, …, Cn are participating.↵
The voter’s preference profile is represented by a permutation of these candidates — this permutation encodes the order from most to least preferred.↵
↵
In addition to the preference order, we are given a cost matrix A of size n × (n − 1), where:↵
↵
A[i][j] = cost of the campaign to shift candidate Ci by j positions upward/downward in the permutation.↵
↵
That is, if candidate Ci currently appears in position p, then moving it to position (p — j) (i.e., moving it up by j ranks) or moving it to position (p + j) incurs a cost of A[i][j]. Note that the relative order of any other candidate does not change in this single operation. So, we may pay a cost of A[3][2] to convert the order {C1, C3, C5, C2, C4} to {C1, C5, C2, C3, C4}.↵
↵
The goal is to make candidate C1 the top-ranked candidate in the preference profile by performing a sequence of shifts (possibly involving other candidates too) while minimizing the total cost.↵
↵
Formally:↵
Find the minimum total cost required to rearrange the permutation such that candidate C1 occupies the first position. (The ranking of other candidates does not matter.)↵
↵
Please let me know if any part of the statement feels ambiguous.↵
I am looking forward to even discuss if you have any ideas or thoughts on a possible solution.
It would be great to hear ideas about possible approaches (right now, I haven’t even been able to come up with a polynomial-time algorithm) or an idea to show its reduction from some NP-hard problem.↵
↵
↵
Consider a single-voter election where a set of candidates C1, C2, …, Cn are participating.↵
The voter’s preference profile is represented by a permutation of these candidates — this permutation encodes the order from most to least preferred.↵
↵
In addition to the preference order, we are given a cost matrix A of size n × (n − 1), where:↵
↵
A[i][j] = cost of the campaign to shift candidate Ci by j positions upward/downward in the permutation.↵
↵
That is, if candidate Ci currently appears in position p, then moving it to position (p — j) (i.e., moving it up by j ranks) or moving it to position (p + j) incurs a cost of A[i][j]. Note that the relative order of any other candidate does not change in this single operation. So, we may pay a cost of A[3][2] to convert the order {C1, C3, C5, C2, C4} to {C1, C5, C2, C3, C4}.↵
↵
The goal is to make candidate C1 the top-ranked candidate in the preference profile by performing a sequence of shifts (possibly involving other candidates too) while minimizing the total cost.↵
↵
Formally:↵
Find the minimum total cost required to rearrange the permutation such that candidate C1 occupies the first position. (The ranking of other candidates does not matter.)↵
↵
Please let me know if any part of the statement feels ambiguous.↵
I am looking forward to even discuss if you have any ideas or thoughts on a possible solution.
