Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userElection with Bribed Voter Uncertainty: Hardness and Approximation Algorithm
48
0
0.0
(
0
)
Added by
Lin Chen
Publication date
2018
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Bribery in election (or computational social choice in general) is an important problem that has received a considerable amount of attention. In the classic bribery problem, the briber (or attacker) bribes some voters in attempting to make the bribers designated candidate win an election. In this paper, we introduce a novel variant of the bribery problem, Election with Bribed Voter Uncertainty or BVU for short, accommodating the uncertainty that the vote of a bribed voter may or may not be counted. This uncertainty occurs either because a bribed voter may not cast its vote in fear of being caught, or because a bribed voter is indeed caught and therefore its vote is discarded. As a first step towards ultimately understanding and addressing this important problem, we show that it does not admit any multiplicative $O(1)$-approximation algorithm modulo standard complexity assumptions. We further show that there is an approximation algorithm that returns a solution with an additive-$epsilon$ error in FPT time for any fixed $epsilon$.
rate research
Read More
The minimum linear ordering problem (MLOP) seeks to minimize an aggregated cost $f(cdot)$ due to an ordering $sigma$ of the items (say $[n]$), i.e., $min_{sigma} sum_{iin [n]} f(E_{i,sigma})$, where $E_{i,sigma}$ is the set of items that are mapped by $sigma$ to indices at most $i$. This problem has been studied in the literature for various special cases of the cost function $f$, and in a general setting for a submodular or supermodular cost $f$ [ITT2012]. Though MLOP was known to be NP-hard for general submodular functions, it was unknown whether the special case of graphic matroid MLOP (with $f$ being the matroid rank function of a graph) was polynomial-time solvable. Following this motivation, we explore related classes of linear ordering problems, including symmetric submodular MLOP, minimum latency vertex cover, and minimum sum vertex cover. We show that the most special cases of our problem, graphic matroid MLOP and minimum latency vertex cover, are both NP-hard. We further expand the toolkit for approximating MLOP variants: using the theory of principal partitions, we show a $2-frac{1+ell_{f}}{1+|E|}$ approximation to monotone submodular MLOP, where $ell_{f}=frac{f(E)}{max_{xin E}f({x})}$ satisfies $1 leq ell_f leq |E|$. Thus our result improves upon the best known bound of $2-frac{2}{1+|E|}$ by Iwata, Tetali, and Tripathi [ITT2012]. This leads to a $2-frac{1+r(E)}{1+|E|}$ approximation for the matroid MLOP, corresponding to the case when $r$ is the rank function of a given matroid. Finally, we show that MLVC can be $4/3$ approximated, matching the integrality gap of its vanilla LP relaxation.
We study approximation algorithms for the problem of minimizing the makespan on a set of machines with uncertainty on the processing times of jobs. In the model we consider, which goes back to~cite{BertsimasS03}, once the schedule is defined an adversary can pick a scenario where deviation is added to some of the jobs processing times. Given only the maximal cardinality of these jobs, and the magnitude of potential deviation for each job, the goal is to optimize the worst-case scenario. We consider both the cases of identical and unrelated machines. Our main result is an EPTAS for the case of identical machines. We also provide a $3$-approximation algorithm and an inapproximability ratio of $2-epsilon$ for the case of unrelated machines
The problem of solving linear systems is one of the most fundamental problems in computer science, where given a satisfiable linear system $(A,b)$, for $A in mathbb{R}^{n times n}$ and $b in mathbb{R}^n$, we wish to find a vector $x in mathbb{R}^n$ such that $Ax = b$. The current best algorithms for solving dense linear systems reduce the problem to matrix multiplication, and run in time $O(n^{omega})$. We consider the problem of finding $varepsilon$-approximate solutions to linear systems with respect to the $L_2$-norm, that is, given a satisfiable linear system $(A in mathbb{R}^{n times n}, b in mathbb{R}^n)$, find an $x in mathbb{R}^n$ such that $||Ax - b||_2 leq varepsilon||b||_2$. Our main result is a fine-grained reduction from computing the rank of a matrix to finding $varepsilon$-approximate solutions to linear systems. In particular, if the best known $O(n^omega)$ time algorithm for computing the rank of $n times O(n)$ matrices is optimal (which we conjecture is true), then finding an $varepsilon$-approximate solution to a dense linear system also requires $tilde{Omega}(n^{omega})$ time, even for $varepsilon$ as large as $(1 - 1/text{poly}(n))$. We also prove (under some modified conjectures for the rank-finding problem) optimal hardness of approximation for sparse linear systems, linear systems over positive semidefinite matrices, well-conditioned linear systems, and approximately solving linear systems with respect to the $L_p$-norm, for $p geq 1$. At the heart of our results is a novel reduction from the rank problem to a decision version of the approximate linear systems problem. This reduction preserves properties such as matrix sparsity and bit complexity.
In mobile wireless sensor networks (MWSNs), each sensor has the ability not only to sense and transmit data but also to move to some specific location. Because the movement of sensors consumes much more power than that in sensing and communication, the problem of scheduling mobile sensors to cover all targets and maintain network connectivity such that the total movement distance of mobile sensors is minimized has received a great deal of attention. However, in reality, due to a limited budget or numerous targets, mobile sensors may be not enough to cover all targets or form a connected network. Therefore, targets must be weighted by their importance. The more important a target, the higher the weight of the target. A more general problem for target coverage and network connectivity, termed the Maximum Weighted Target Coverage and Sensor Connectivity with Limited Mobile Sensors (MWTCSCLMS) problem, is studied. In this paper, an approximation algorithm, termed the weighted-maximum-coverage-based algorithm (WMCBA), is proposed for the subproblem of the MWTCSCLMS problem. Based on the WMCBA, the Steiner-tree-based algorithm (STBA) is proposed for the MWTCSCLMS problem. Simulation results demonstrate that the STBA provides better performance than the other methods.
This paper describes a simple greedy D-approximation algorithm for any covering problem whose objective function is submodular and non-decreasing, and whose feasible region can be expressed as the intersection of arbitrary (closed upwards) covering constraints, each of which constrains at most D variables of the problem. (A simple example is Vertex Cover, with D = 2.) The algorithm generalizes previous approximation algorithms for fundamental covering problems and online paging and caching problems.
suggested questions
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
