On the cut-query complexity of approximating max-cut
From MaRDI portal
Cites work
- A faster cutting plane method and its implications for combinatorial and convex optimization
- A query algorithm for learning a spanning forest in weighted undirected graphs
- A tight linear time (1/2)-approximation for unconstrained submodular maximization
- Computing exact minimum cuts without knowing the graph
- Cut query algorithms with star contraction
- Deterministic Algorithms for Submodular Maximization Problems
- Graph connectivity and single element recovery via linear and OR queries
- scientific article; zbMATH DE number 5485589 (Why is no real title available?)
- scientific article; zbMATH DE number 7053292 (Why is no real title available?)
- scientific article; zbMATH DE number 7788399 (Why is no real title available?)
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Maximizing Non-monotone Submodular Functions
- Nearly optimal communication and query complexity of bipartite matching
- New Query Lower Bounds for Submodular Function Minimization
- On Parity Check (0,1)-Matrix over $\mathbb{Z}_p$
- On the cut dimension of a graph
- On the power of unique 2-prover 1-round games
- Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
- Optimal reconstruction of graphs under the additive model
- Querying a Matrix Through Matrix-Vector Products.
- Randomized approximation schemes for cuts and flows in capacitated graphs
- Single pass spectral sparsification in dynamic streams
- Some optimal inapproximability results
- Sparse sums of positive semidefinite matrices
- Spectral sparsification in dynamic graph streams
- Toward a deterministic polynomial time algorithm with optimal additive query complexity
- Twice-Ramanujan sparsifiers
- Weighted min-cut: sequential, cut-query, and streaming algorithms
Cited in
(1)- Cut-query algorithms with few rounds
This page was built for publication: On the cut-query complexity of approximating max-cut
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6875074)
