Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userSmoothed complexity of local Max-Cut and binary Max-CSP
96
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We show that the smoothed complexity of the FLIP algorithm for local Max-Cut is at most $smash{phi n^{O(sqrt{log n})}}$, where $n$ is the number of nodes in the graph and $phi$ is a parameter that measures the magnitude of perturbations applied on its edge weights. This improves the previously best upper bound of $phi n^{O(log n)}$ by Etscheid and R{o}glin. Our result is based on an analysis of long sequences of flips, which shows~that~it is very unlikely for every flip in a long sequence to incur a positive but small improvement in the cut weight. We also extend the same upper bound on the smoothed complexity of FLIP to all binary Maximum Constraint Satisfaction Problems.
rate research
Read More
In this work, we initiate the study of fault tolerant Max Cut, where given an edge-weighted undirected graph $G=(V,E)$, the goal is to find a cut $Ssubseteq V$ that maximizes the total weight of edges that cross $S$ even after an adversary removes $k$ vertices from $G$. We consider two types of adversaries: an adaptive adversary that sees the outcome of the random coin tosses used by the algorithm, and an oblivious adversary that does not. For any constant number of failures $k$ we present an approximation of $(0.878-epsilon)$ against an adaptive adversary and of $alpha_{GW}approx 0.8786$ against an oblivious adversary (here $alpha_{GW}$ is the approximation achieved by the random hyperplane algorithm of [Goemans-Williamson J. ACM `95]). Additionally, we present a hardness of approximation of $alpha_{GW}$ against both types of adversaries, rendering our results (virtually) tight. The non-linear nature of the fault tolerant objective makes the design and analysis of algorithms harder when compared to the classic Max Cut. Hence, we employ approaches ranging from multi-objective optimization to LP duality and the ellipsoid algorithm to obtain our results.
MAX CLIQUE problem (MCP) is an NPO problem, which asks to find the largest complete sub-graph in a graph $G, G = (V, E)$ (directed or undirected). MCP is well known to be $NP-Hard$ to approximate in polynomial time with an approximation ratio of $1 + epsilon$, for every $epsilon > 0$ [9] (and even a polynomial time approximation algorithm with a ratio $n^{1 - epsilon}$ has been conjectured to be non-existent [2] for MCP). Up to this date, the best known approximation ratio for MCP of a polynomial time algorithm is $O(n(log_2(log_2(n)))^2 / (log_2(n))^3)$ given by Feige [1]. In this paper, we show that MCP can be approximated with a constant factor in polynomial time through approximation ratio preserving reductions from MCP to MAX DNF and from MAX DNF to MIN SAT. A 2-approximation algorithm for MIN SAT was presented in [6]. An approximation ratio preserving reduction from MIN SAT to min vertex cover improves the approximation ratio to $2 - Theta(1/ sqrt{n})$ [10]. Hence we prove false the infamous conjecture, which argues that there cannot be a polynomial time algorithm for MCP with an approximation ratio of any constant factor.
In 2013, Orlin proved that the max flow problem could be solved in $O(nm)$ time. His algorithm ran in $O(nm + m^{1.94})$ time, which was the fastest for graphs with fewer than $n^{1.06}$ arcs. If the graph was not sufficiently sparse, the fastest running time was an algorithm due to King, Rao, and Tarjan. We describe a new variant of the excess scaling algorithm for the max flow problem whose running time strictly dominates the running time of the algorithm by King et al. Moreover, for graphs in which $m = O(n log n)$, the running time of our algorithm dominates that of King et al. by a factor of $O(loglog n)$.
We recently introduced the graph invariant twin-width, and showed that first-order model checking can be solved in time $f(d,k)n$ for $n$-vertex graphs given with a witness that the twin-width is at most $d$, called $d$-contraction sequence or $d$-sequence, and formulas of size $k$ [Bonnet et al., FOCS 20]. The inevitable price to pay for such a general result is that $f$ is a tower of exponentials of height roughly $k$. In this paper, we show that algorithms based on twin-width need not be impractical. We present $2^{O(k)}n$-time algorithms for $k$-Independent Set, $r$-Scattered Set, $k$-Clique, and $k$-Dominating Set when an $O(1)$-sequence is provided. We further show how to solve weighted $k$-Independent Set, Subgraph Isomorphism, and Induced Subgraph Isomorphism, in time $2^{O(k log k)}n$. These algorithms are based on a dynamic programming scheme following the sequence of contractions forward. We then show a second algorithmic use of the contraction sequence, by starting at its end and rewinding it. As an example, we establish that bounded twin-width classes are $chi$-bounded. This significantly extends the $chi$-boundedness of bounded rank-width classes, and does so with a very concise proof. The third algorithmic use of twin-width builds on the second one. Playing the contraction sequence backward, we show that bounded twin-width graphs can be edge-partitioned into a linear number of bicliques, such that both sides of the bicliques are on consecutive vertices, in a fixed vertex ordering. Given that biclique edge-partition, we show how to solve the unweighted Single-Source Shortest Paths and hence All-Pairs Shortest Paths in sublinear time $O(n log n)$ and time $O(n^2 log n)$, respectively. Finally we show that Min Dominating Set and related problems have constant integrality gaps on bounded twin-width classes, thereby getting constant approximations on these classes.
The classical max-flow min-cut theorem describes transport through certain idealized classical networks. We consider the quantum analog for tensor networks. By associating an integral capacity to each edge and a tensor to each vertex in a flow network, we can also interpret it as a tensor network, and more specifically, as a linear map from the input space to the output space. The quantum max flow is defined to be the maximal rank of this linear map over all choices of tensors. The quantum min cut is defined to be the minimum product of the capacities of edges over all cuts of the tensor network. We show that unlike the classical case, the quantum max-flow=min-cut conjecture is not true in general. Under certain conditions, e.g., when the capacity on each edge is some power of a fixed integer, the quantum max-flow is proved to equal the quantum min-cut. However, concrete examples are also provided where the equality does not hold. We also found connections of quantum max-flow/min-cut with entropy of entanglement and the quantum satisfiability problem. We speculate that the phenomena revealed may be of interest both in spin systems in condensed matter and in quantum gravity.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
