We study the computational complexity of committee selection problem for several approval-based voting rules in the presence of outliers. Our first result shows that outlier consideration makes committee selection problem intractable for approval, net approval, and minisum approval voting rules. We then study parameterized complexity of this problem with five natural parameters, namely the target score, the size of the committee (and its dual parameter, the number of candidates outside the committee), the number of outliers (and its dual parameter, the number of non-outliers). For net approval and minisum approval voting rules, we provide a dichotomous result, resolving the parameterized complexity of this problem for all subsets of five natural parameters considered (by showing either FPT or W[1]-hardness for all subsets of parameters). For the approval voting rule, we resolve the parameterized complexity of this problem for all subsets of parameters except one. We also study approximation algorithms for this problem. We show that there does not exist any alpha(.) factor approximation algorithm for approval and net approval voting rules, for any computable function alpha(.), unless P=NP. For the minisum voting rule, we provide a pseudopolynomial (1+eps) factor approximation algorithm.
In the minimax notion of distance, the problem of finding a closest string in the presence of outliers was initiated in @cite_29 , and was further refined in @cite_30 . The work in @cite_30 demonstrates hardness of approximation for variations involving outliers. With the minisum notion of distance, the study of finding the best string with respect to outliers was studied in @cite_7 . In contrast with the minimax rule, this work shows a PTAS for .
@cite_30 @cite_29 @cite_7
2963006872 2047386086 1990630682 2180828828
In the Closest String problem one is given a family S of equal-length strings over some fixed alphabet, and the task is to find a string y that minimizes the maximum Hamming distance between y and a string from S. While polynomial-time approximation schemes (PTASes) for this problem are known for a long time [; J. ACM'02], no efficient polynomial-time approximation scheme (EPTAS) has been proposed so far. In this paper, we prove that the existence of an EPTAS for Closest String is in fact unlikely, as it would imply that FPT=W[1], a highly unexpected collapse in the hierarchy of parameterized complexity classes. Our proof also shows that the existence of a PTAS for Closest String with running time f(eps) n^o(1 eps), for any computable function f, would contradict the Exponential Time Hypothesis. The problem of finding a center string that is "close" to everygiven string arises in computational molecular biology and codingtheory. This problem has two versions: the Closest String problemand the Closest Substring problem. Given a set of strings S= s1, s2, ...,sn , each of length m, the Closest Stringproblem is to find the smallest d and a string s of lengthm which is within Hamming distance d to eachsi e S. This problem comes fromcoding theory when we are looking for a code not too far away froma given set of codes. Closest Substring problem, with an additionalinput integer L, asks for the smallest d and a strings, of length L, which is within Hamming distance daway from a substring, of length L, of each si. This problemis much more elusive than the Closest String problem. The ClosestSubstring problem is formulated from applications in findingconserved regions, identifying genetic drug targets and generatinggenetic probes in molecular biology. Whether there are efficientapproximation algorithms for both problems are major open questionsin this area. We present two polynomial-time approximationalgorithms with approximation ratio 1 + e for any smalle to settle both questions. This paper presents a new method of locating n new facilities among m destinations in accordance with the minimax criterion; that is, the facilities are located to minimize the maximum weighted distance in the system. Distances may be rectangular, Euclidean, or general (lp). The method involves the numerical integration of ordinary differential equations and is computationally superior to methods using nonlinear programming. Many problems in bioinformatics are about finding strings that approximately represent a collection of given strings. We look at more general problems where some input strings can be classified as outliers. The Close to Most Strings problem is, given a set S of the same-length strings, and a parameter d, find a string x that maximizes the number of ''non-outliers'' within Hamming distance d of x. We prove that this problem has no polynomial-time approximation scheme (PTAS) unless NP has randomized polynomial-time algorithms, correcting a decade-old erroneous proof made previously in the literature. The Most Strings with Few Bad Columns problem is to find a maximum-size subset of input strings so that the number of non-identical positions is at most k; we show it has no PTAS unless P=NP. We also observe Closest to k Strings has no efficient PTAS (EPTAS) unless a parameterized complexity hierarchy collapses. In sum, outliers help model problems associated with using biological data, but we show the problem of finding an approximate solution is computationally difficult.