MAX-CUT on Samplings of Dense Graphs
2022 19th International Joint Conference on Computer Science and Software Engineering (JCSSE)(2022)
摘要
The maximum cut problem finds a partition of a graph that maximizes the number of crossing edges. When the graph is dense or is sampled based on certain planted assumptions, there exist polynomial-time approximation schemes that given a fixed
$\epsilon > 0$
., find a solution whose value is at least
$1-\epsilon$
of the optimal value. This paper presents another random model relating to both successful cases. Consider an n-vertex graph
$G$
whose edges are sampled from an unknown dense graph
$H$
independently with probability
$p=\Omega(1/\sqrt{\log n});$
this input graph
$G$
has
$O(n^{2}/\sqrt{\log n})$
edges and is no longer dense. We show how to modify a PTAS by de la Vega for dense graphs to find an
$(1-\epsilon)$
-approximate solution for
$G$
. Although our algorithm works for a very narrow range of sampling probability
$p$
, the sampling model itself generalizes the planted models fairly well.
更多查看译文
关键词
dense graphs,sampling probability,sampling model,planted models,MAX-CUT,samplings,maximum cut problem,crossing edges,planted assumptions,polynomial-time approximation schemes,n-vertex graph
AI 理解论文
溯源树
样例
生成溯源树,研究论文发展脉络
Chat Paper
正在生成论文摘要