Hardness of fully dense problems

DOI10.1016/J.IC.2007.02.006zbMATH Open1121.68054OpenAlexW2001866149WikidataQ56486199 ScholiaQ56486199MaRDI QIDQ2643075FDOQ2643075

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

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

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)

Cites Work

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

Cited In (14)

• 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
• Title not available (Why is that?)
• Polynomial time approximation schemes for some dense instances of NP-hard optimization problems
• On random betweenness constraints
• An updated survey on the linear ordering problem for weighted or unweighted tournaments
• 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
• The Complexity and Distribution of Hard Problems

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)