The importance of being biased
From MaRDI portal
Publication:3579199
DOI10.1145/509907.509915zbMath1192.68318OpenAlexW2028146521WikidataQ59650038 ScholiaQ59650038MaRDI QIDQ3579199
Publication date: 5 August 2010
Published in: Proceedings of the thiry-fourth annual ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/509907.509915
Related Items
Approximation algorithms for the maximum vertex coverage problem on bounded degree graphs ⋮ Complexity of approximating bounded variants of optimization problems ⋮ An edge-reduction algorithm for the vertex cover problem ⋮ Inapproximability results for equations over finite groups ⋮ Approximation hardness of edge dominating set problems ⋮ From the quantum approximate optimization algorithm to a quantum alternating operator ansatz ⋮ Gaussian bounds for noise correlation of functions ⋮ Approximating the minimum weight weak vertex cover ⋮ Minimum 2SAT-DELETION: Inapproximability results and relations to minimum vertex cover ⋮ Testing juntas ⋮ Super-polynomial approximation branching algorithms ⋮ Parameterized complexity and inapproximability of dominating set problem in chordal and near chordal graphs ⋮ Graph covering using bounded size subgraphs ⋮ A parameterized approximation scheme for generalized partial vertex cover ⋮ On the Minimum Hitting Set of Bundles Problem ⋮ Mathematics of computation through the lens of linear equations and lattices ⋮ A primal-dual approximation algorithm for the vertex cover \(P^3\) problem ⋮ Confronting intractability via parameters ⋮ On the advantage of overlapping clusters for minimizing conductance ⋮ On finding the longest antisymmetric path in directed acyclic graphs ⋮ Maximum locally stable matchings ⋮ Parameterized lower bound and inapproximability of polylogarithmic string barcoding ⋮ Online budgeted maximum coverage ⋮ Non-interactive correlation distillation, inhomogeneous Markov chains, and the reverse Bonami-Beckner inequality ⋮ Crown reductions for the minimum weighted vertex cover problem ⋮ Approximation hardness of dominating set problems in bounded degree graphs ⋮ Parameterized approximability of maximizing the spread of influence in networks ⋮ On the measure of intersecting families, uniqueness and stability ⋮ Metrical service systems with multiple servers ⋮ Minimum vertex cover in rectangle graphs ⋮ Inapproximability results for equations over infinite groups ⋮ On approximating minimum vertex cover for graphs with perfect matching ⋮ Linear time algorithms for approximating the facility terminal cover problem ⋮ The checkpoint problem ⋮ On the independent set problem in random graphs ⋮ Upper and lower bounds on approximating weighted mixed domination ⋮ Envy-freeness and relaxed stability: hardness and approximation algorithms ⋮ Approximating the Influence of Monotone Boolean Functions in $O(\sqrt{n})$ Query Complexity ⋮ Using the FGLSS-Reduction to Prove Inapproximability Results for Minimum Vertex Cover in Hypergraphs ⋮ On the induced matching problem in Hamiltonian bipartite graphs ⋮ On problems without polynomial kernels ⋮ On the minimum hitting set of bundles problem ⋮ A simple rounding scheme for multistage optimization ⋮ Priority algorithms for graph optimization problems ⋮ A Katona-type proof of an Erdős-Ko-Rado-type theorem ⋮ New results on polynomial inapproximability and fixed parameter approximability of Edge Dominating Set
