Hardness of fully dense problems

DOI10.1016/J.IC.2007.02.006MaRDI QIDQ2643075zbMATH OpenOpenAlexWikidataFDO

Authors Nir Ailon, Noga Alon

Publication date 23 August 2007

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ic.2007.02.006

zbMATH Keywords

NP-hardnessdense problems

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Recommendations

• Hard-core theorems for complexity classes
• The Complexity and Distribution of Hard Problems
• Hardness of approximation
• scientific article; zbMATH DE number 1263204
• Hardness results for structured linear systems
• Covering Problems with Hard Capacities
• Algorithms – ESA 2004
• scientific article; zbMATH DE number 1775419
• On the approximation hardness of dense TSP and other path problems
• scientific article; zbMATH DE number 403953

Cites work

• scientific article; zbMATH DE number 1256685 (Why is no real title available?)
• scientific article; zbMATH DE number 1263204 (Why is no real title available?)
• A Geometric Approach to Betweenness
• A Polynomial Algorithm for the 2-Path Problem for Semicomplete Digraphs
• Additive approximation for edge-deletion problems
• Aggregating inconsistent information
• Approximating minimum feedback sets and multicuts in directed graphs
• Eigenvalues, geometric expanders, sorting in rounds, and Ramsey theory
• MAX-CUT has a randomized approximation scheme in dense graphs
• Packing directed circuits fractionally
• Polynomial time approximation schemes for some dense instances of NP-hard optimization problems
• Quick approximation to matrices and applications
• Random sampling and approximation of MAX-CSP problems
• Ranking Tournaments
• Tensor decomposition and approximation schemes for constraint satisfaction problems
• The Minimum Feedback Arc Set Problem is NP-Hard for Tournaments
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Total Ordering Problem

Cited in

(14)

• The Complexity and Distribution of Hard Problems
• New results on optimizing rooted triplets consistency
• Linear kernel for \textsc{Rooted Triplet Inconsistency} and other problems based on conflict packing technique
• Voting procedures, complexity of
• On the kernelization of ranking \(r\)-CSPs: linear vertex-kernels for generalizations of feedback arc set and betweenness in tournaments
• Approximation schemes for the betweenness problem in tournaments and related ranking problems
• Almost \(k\)-wise vs. \(k\)-wise independent permutations, and uniformity for general group actions
• scientific article; zbMATH DE number 7758347 (Why is no real title available?)
• Polynomial time approximation schemes for some dense instances of NP-hard optimization problems
• An updated survey on the linear ordering problem for weighted or unweighted tournaments
• On random betweenness constraints
• Problems and conjectures concerning connectivity, paths, trees and cycles in tournament-like digraphs
• A survey on the linear ordering problem for weighted or unweighted tournaments
• On Random Ordering Constraints

This page was built for publication: Hardness of fully dense problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2643075)