Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userMax-Cut via Kuramoto-type Oscillators
97
0
0.0
(
0
)
Added by
Stefan Steinerberger
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Authors
Stefan Steinerberger
Ask ChatGPT about the research
No Arabic abstract
We consider the Max-Cut problem. Let $G = (V,E)$ be a graph with adjacency matrix $(a_{ij})_{i,j=1}^{n}$. Burer, Monteiro & Zhang proposed to find, for $n$ angles $left{theta_1, theta_2, dots, theta_nright} subset [0, 2pi]$, minima of the energy $$ f(theta_1, dots, theta_n) = sum_{i,j=1}^{n} a_{ij} cos{(theta_i - theta_j)}$$ because configurations achieving a global minimum leads to a partition of size 0.878 Max-Cut(G). This approach is known to be computationally viable and leads to very good results in practice. We prove that by replacing $cos{(theta_i - theta_j)}$ with an explicit function $g_{varepsilon}(theta_i - theta_j)$ global minima of this new functional lead to a $(1-varepsilon)$Max-Cut(G). This suggests some interesting algorithms that perform well. It also shows that the problem of finding approximate global minima of energy functionals of this type is NP-hard in general.
rate research
Read More
We show that the linear or quadratic 0/1 program[P:quadmin{ c^Tx+x^TFx : :A,x =b;:xin{0,1}^n},]can be formulated as a MAX-CUT problem whose associated graph is simply related to the matrices $F$ and $A^TA$.Hence the whole arsenal of approximation techniques for MAX-CUT can be applied. We also compare the lower boundof the resulting semidefinite (or Shor) relaxation with that of the standard LP-relaxation and the first semidefinite relaxationsassociated with the Lasserre hierarchy and the copositive formulations of $P$.
The max-cut problem is a classical graph theory problem which is NP-complete. The best polynomial time approximation scheme relies on emph{semidefinite programming} (SDP). We study the conditions under which graphs of certain classes have rank~1 solutions to the max-cut SDP. We apply these findings to look at how solutions to the max-cut SDP behave under simple combinatorial constructions. Our results determine when solutions to the max-cut SDP for cycle graphs are rank~1. We find the solutions to the max-cut SDP of the vertex~sum of two graphs. We then characterize the SDP solutions upon joining two triangle graphs by an edge~sum.
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.
Many coordination phenomena are based on a synchronisation process, whose global behaviour emerges from the interactions among the individual parts. Often in Nature, such self-organising mechanism allows the system to behave as a whole and thus grounding its very first existence, or expected functioning, on such process. There are however cases where synchronisation acts against the stability of the system; for instance in the case of engineered structures, resonances among sub parts can destabilise the whole system. In this Letter we propose an innovative control method to tackle the synchronisation process based on the use of the Hamiltonian control theory, by adding a small control term to the system we are able to impede the onset of the synchronisation. We present our results on the paradigmatic Kuramoto model but the applicability domain is far more large.
The Potts model has many applications. It is equivalent to some min-cut and max-flow models. Primal-dual algorithms have been used to solve these problems. Due to the special structure of the models, convergence proof is still a difficult problem. In this work, we developed two novel, preconditioned, and over-relaxed alternating direction methods of multipliers (ADMM) with convergence guarantee for these models. Using the proposed preconditioners or block preconditioners, we get accelerations with the over-relaxation variants of preconditioned ADMM. The preconditioned and over-relaxed Douglas-Rachford splitting methods are also considered for the Potts model. Our framework can handle both the two-labeling or multi-labeling problems with appropriate block preconditioners based on Eckstein-Bertsekas and Fortin-Glowinski splitting techniques.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
