scientific article; zbMATH DE number 1263204
From MaRDI portal
Publication:4234075
Recommendations
- Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
- Polynomial time approximation schemes for some dense instances of NP-hard optimization problems
- Polynomial time approximation schemes for dense instances of minimum constraint satisfaction
- Sub-exponential approximation schemes for CSPs: from dense to almost sparse
- scientific article; zbMATH DE number 1496577
Cited in
(64)- Balanced cut approximation in random geometric graphs
- Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
- Constructing the highest degree subgraph for dense graphs is in \({\mathcal N}{\mathcal C}{\mathcal A}{\mathcal S}\)
- An improved approximation algorithm of MULTIWAY CUT.
- Fast stabbing of boxes in high dimensions
- A randomized approximation scheme for metric MAX-CUT
- Complexity of finding dense subgraphs
- Parallel approximation schemes for a class of planar and near planar combinatorial optimization problems.
- Approximate and dynamic rank aggregation
- Bounds on the max and min bisection of random cubic and random 4-regular graphs
- Random sampling and approximation of MAX-CSPs
- Improved non-approximability results for minimum vertex cover with density constraints
- A simple algorithm for the multiway cut problem
- Near optimal solutions for maximum quasi-bicliques
- Finding connected \(k\)-subgraphs with high density
- The densest \(k\)-subgraph problem on clique graphs
- A multiple penalty function method for solving max-bisection problems
- Hardness of fully dense problems
- Chromatic kernel and its applications
- Algorithms for graph partitioning on the planted partition model
- Tight complexity bounds for FPT subgraph problems parameterized by clique-width
- On the efficiency of polynomial time approximation schemes
- A lower bound of \(8/(7+\frac{1}{k-1})\) on the integrality ratio of the Călinescu-Karloff-Rabani relaxation for multiway cut
- Finding Connected Dense k-Subgraphs
- Approximation schemes via Sherali-Adams hierarchy for dense constraint satisfaction problems and assignment problems
- How to Cut a Graph into Many Pieces
- Approximation schemes for the betweenness problem in tournaments and related ranking problems
- String-matching and alignment algorithms for finding motifs in NGS data
- Sampling subproblems of heterogeneous Max-Cut problems and approximation algorithms
- Parallel approximation to high multiplicity scheduling problemsVIAsmooth multi-valued quadratic programming
- Testability of minimum balanced multiway cut densities
- scientific article; zbMATH DE number 1301970 (Why is no real title available?)
- Polynomial time approximation schemes for dense instances of minimum constraint satisfaction
- Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : de la structure de NPO à la structure des instances
- scientific article; zbMATH DE number 1496577 (Why is no real title available?)
- Simplex partitioning via exponential clocks and the multiway-cut problem
- Sub-exponential approximation schemes for CSPs: from dense to almost sparse
- Integer and fractional packings in dense 3‐uniform hypergraphs
- Sublinear algorithms for MAXCUT and correlation clustering
- Greedily finding a dense subgraph
- A polynomial-time algorithm to determine (almost) Hamiltonicity of dense regular graphs
- New abilities and limitations of spectral graph bisection
- Amplification and Derandomization without Slowdown
- Mathematical Foundations of Computer Science 2004
- An Efficient Algorithm for Enumerating Pseudo Cliques
- A new Lagrangian net algorithm for solving max-bisection problems
- Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
- Maximum dispersion problem in dense graphs
- On the parallel approximability of a subclass of quadratic programming.
- On point covers of c-oriented polygons
- Polynomial time approximation schemes for some dense instances of NP-hard optimization problems
- Partitioning problems in dense hypergraphs
- The algebraic structure of the densification and the sparsification tasks for CSPs
- Improved non-approximability results for vertex cover with density constraints
- Improved approximation algorithms for MAX k-cut and MAX BISECTION
- Linear contracts for supermodular functions based on graphs
- A spectral approach to approximately counting independent sets in dense bipartite graphs
- Approximation algorithms on k-correlation clustering of uniform hypergraphs
- A simple approximation algorithm for k-correlation clustering on uniform hypergraphs
- Min-CSPs on complete instances. II: Polylogarithmic approximation for Min-NAE-3-SAT
- Spectral refutations of semirandom k-LIN over larger fields
- An efficient algorithm for solving pseudo clique enumeration problem
- Integer and fractional packings of hypergraphs
- A constant approximation algorithm for the densest \(k\)-subgraph problem on chordal graphs
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4234075)
