Frontiers of Algorithmics

We revisit pool block withholding (PBW) attack in this work, while taking miners’ rationality into consideration. It has been shown that a malicious mining pool in Bitcoin may attack other pools by sending some dummy miners who do not reveal true solutions but obtain reward portions from attacked pools. This result assumes that the infiltrating miners are always loyal and behave as the malicious pool desires; but why? In this work, we study rational infiltrating miners who behave by maximizing their own utilities. We characterize the infiltrating miners’ optimal strategies for two kinds of betraying behaviors depending on whether they return to the original pool or not. Our characterizations show that the infiltrating miners’ optimal strategy is simple and binary: they either betray or stay loyal all together, which depends on the total amount of them sent out by the malicious pool. Accordingly, we further compute the pool’s optimal attacking strategy given the miners’ strategic behaviors. Our experiments also show that by launching PBW attacks, the benefit to a pool is actually incremental.

Given a digraph \(G = (V, E)\), the k-path partition problem is to find a minimum collection of vertex-disjoint directed paths each of order at most k to cover all the vertices of V. The problem has various applications in facility location, network monitoring, transportation and others. Its special case on undirected graphs has received much attention recently, but the general version is seemingly untouched in the literature. We present the first k/2-approximation algorithm, for any \(k \ge 3\), based on a novel concept of augmenting path to minimize the number of singletons in the partition. When \(k \ge 7\), we present an improved \((k+2)/3\)-approximation algorithm based on the maximum path-cycle cover followed by a careful 2-cycle elimination process. When \(k = 3\), we define the second novel kind of augmenting paths to reduce the number of 2-paths and propose an improved 13/9-approximation algorithm.

We present new, faster pseudopolynomial time algorithms for the \(k\text {-}\textsc {Subset}\,\textsc {Sum}\) problem, defined as follows: given a set Z of n positive integers and k targets \(t_1, \ldots , t_k\), determine whether there exist k disjoint subsets \(Z_1,\dots ,Z_k \subseteq Z\), such that \(\varSigma (Z_i) = t_i\), for \(i = 1, \ldots , k\). Assuming \(t = \max \{ t_1, \ldots , t_k \}\) is the maximum among the given targets, a standard dynamic programming approach based on Bellman’s algorithm [3] can solve the problem in \(O(n t^k)\) time. We build upon recent advances on \(\textsc {Subset}\,\textsc {Sum}\) due to Koiliaris and Xu [16] and Bringmann [4] in order to provide faster algorithms for \(k\text {-}\textsc {Subset}\,\textsc {Sum}\). We devise two algorithms: a deterministic one of time complexity \(\tilde{O}(n^{k / (k+1)} t^k)\) and a randomised one of \(\tilde{O}(n + t^k)\) complexity.

We further demonstrate how these algorithms can be used in order to cope with variations of \(k\text {-}\textsc {Subset}\,\textsc {Sum}\), namely \(\textsc {Subset}\,\textsc {Sum}\,\textsc {Ratio}\), \(k\text {-}\textsc {Subset}\,\textsc {Sum}\,\textsc {Ratio}\) and \(\textsc {Multiple}\,\textsc {Subset}\,\textsc {Sum}\).

In this paper, we study a generalization of the classic bribery problem known as electoral manipulation under media influence (EMMI). This model is motivated by modern political campaigns where candidates try to convince voters through advertising in media (TV, newspaper, Internet). When compared with the classical bribery problem, the attacker in this setting cannot directly change opinions of individual voters, but instead can execute influences via a set of manipulation strategies (e.g., advertising on a TV channel). Different manipulation strategies incur different costs and influence different subsets of voters. Once receiving a significant amount of influence, a voter will change opinion. To characterize the opinion change of each voter, we adopt the well-accepted threshold model. We prove the NP-hardness of the EMMI problem and give a dynamic programming algorithm that runs in polynomial time for a restricted case of the EMMI problem.

Multiprocessor scheduling, also called scheduling on parallel identical machines to minimize the makespan, is a classic optimization problem that has received numerous studies. Scheduling with testing is an online variant where the processing time of a job is revealed by an extra test operation, or otherwise the job has to be executed for a given upper bound on the processing time. Albers and Eckl recently studied the multiprocessor scheduling with testing; among others, for the non-preemptive setting they presented an approximation algorithm with competitive ratio approaching 3.1016 when the number of machines tends to infinity and an improved approximation algorithm with competitive ratio approaching 3 when all test operations take a time unit. We propose to first sort the jobs into the non-increasing order of the minimum value between the upper bound and the testing time, then partition the jobs into three groups and process them group by group according to the sorted job order. We show that our algorithm achieves improved competitive ratios, which approach 2.9513 when the number of machines tends to infinity in the general case; when all test operations take a time unit, our algorithm achieves even better competitive ratios approaching 2.8081.