An official website of the United States government
Assuming the Unique Games Conjecture (UGC), the best approximation ratio that can be obtained in polynomial time for the MAX CUT problem is αCUT ≃ 0.87856, obtained by the celebrated SDP-based approximation algorithm of Goemans and Williamson. The currently best approximation algorithm for MAX DI-CUT, i.e., the MAX CUT problem in directed graphs, achieves a ratio of about 0.87401, leaving open the question whether MAX DI-CUT can be approximated as well as MAX CUT. We obtain a slightly improved algorithm for MAX DI-CUT and a new UGC-hardness result for it, showing that 0.87446 ≤ αDI-CUT ≤ 0.87461, where αDI-CUT is the best approximation ratio that can be obtained in polynomial time for MAX DI-CUT under UGC. The new upper bound separates MAX DI-CUT from MAX CUT, resolving a question raised by Feige and Goemans. A natural generalization of MAX DI-CUT is the MAX 2-AND problem in which each constraint is of the form z1∧z2, where z1 and z2 are literals, i.e., variables or their negations (In MAX DI-CUT each constraint is of the form \neg{x1}∧x2, where x1 and x2 are variables.) Austrin separated MAX 2-AND from MAX CUT by showing that α2AND < 0.87435 and conjectured that MAX 2-AND and MAX DI-CUT have the same approximation ratio. Our new lower bound on MAX DI-CUT refutes this conjecture, completing the separation of the three problems MAX 2-AND, MAX DI-CUT and MAX CUT. We also obtain a new lower bound for MAX 2-AND, showing that 0.87414 ≤ α2AND ≤ 0.87435. Our upper bound on MAX DI-CUT is achieved via a simple, analytical proof. The lower bounds on MAX DI-CUT and MAX 2-AND (the new approximation algorithms) use experimentally-discovered distributions of rounding functions which are then verified via computer-assisted proofs.
more »
« less
On the behavior of 1-Laplacian ratio cuts on nearly rectangular domains
Abstract The $$p$$-Laplacian has attracted more and more attention in data analysis disciplines in the past decade. However, there is still a knowledge gap about its behavior, which limits its practical application. In this paper, we are interested in its iterative behavior in domains contained in two-dimensional Euclidean space. Given a connected set $$\varOmega _0 \subset \mathbb{R}^2$$, define a sequence of sets $$(\varOmega _n)_{n=0}^{\infty }$$ where $$\varOmega _{n+1}$$ is the subset of $$\varOmega _n$$ where the first eigenfunction of the (properly normalized) Neumann $$p$$-Laplacian $$ -\varDelta ^{(p)} \phi = \lambda _1 |\phi |^{p-2} \phi $$ is positive (or negative). For $p=1$, this is also referred to as the ratio cut of the domain. We conjecture that these sets converge to the set of rectangles with eccentricity bounded by 2 in the Gromov–Hausdorff distance as long as they have a certain distance to the boundary $$\partial \varOmega _0$$. We establish some aspects of this conjecture for $p=1$ where we prove that (1) the 1-Laplacian spectral cut of domains sufficiently close to rectangles is a circular arc that is closer to flat than the original domain (leading eventually to quadrilaterals) and (2) quadrilaterals close to a rectangle of aspect ratio $$2$$ stay close to quadrilaterals and move closer to rectangles in a suitable metric. We also discuss some numerical aspects and pose many open questions.
more »
« less
- PAR ID:
- 10205611
- Publisher / Repository:
- Oxford University Press
- Date Published:
- Journal Name:
- Information and Inference: A Journal of the IMA
- ISSN:
- 2049-8772
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
null (Ed.)We examine the axisymmetric and non-axisymmetric flows of thin fluid films over a spherical glass dome. A thin film is formed by raising a submerged dome through a silicone oil mixture composed of a volatile, low surface tension species (1 cSt, solvent) and a non-volatile species at a higher surface tension (5 cSt, initial solute volume fraction $$\phi _0$$ ). Evaporation of the 1 cSt silicone oil establishes a concentration gradient and, thus, a surface tension gradient that drives a Marangoni flow that leads to the formation of an initially axisymmetric mound. Experimentally, when $$\phi _0 \leqslant 0.3\,\%$$ , the mound grows axisymmetrically for long times (Rodríguez-Hakim et al. , Phys. Rev. Fluids , vol. 4, 2019, pp. 1–22), whereas when $$\phi _0 \geqslant 0.35\,\%$$ , the mound discharges in a preferred direction, thereby breaking symmetry. Using lubrication theory and numerical solutions, we demonstrate that, under the right conditions, external disturbances can cause an imbalance between the Marangoni flow and the capillary flow, leading to symmetry breaking. In both experiments and simulations, we observe that (i) the apparent, most amplified disturbance has an azimuthal wavenumber of unity, and (ii) an enhanced Marangoni driving force (larger $$\phi _0$$ ) leads to an earlier onset of the instability. The linear stability analysis shows that capillarity and diffusion stabilize the system, while Marangoni driving forces contribute to the growth in the disturbances.more » « less
-
Abstract Let$$\phi $$ be a positive map from the$$n\times n$$ matrices$$\mathcal {M}_n$$ to the$$m\times m$$ matrices$$\mathcal {M}_m$$ . It is known that$$\phi $$ is 2-positive if and only if for all$$K\in \mathcal {M}_n$$ and all strictly positive$$X\in \mathcal {M}_n$$ ,$$\phi (K^*X^{-1}K) \geqslant \phi (K)^*\phi (X)^{-1}\phi (K)$$ . This inequality is not generally true if$$\phi $$ is merely a Schwarz map. We show that the corresponding tracial inequality$${{\,\textrm{Tr}\,}}[\phi (K^*X^{-1}K)] \geqslant {{\,\textrm{Tr}\,}}[\phi (K)^*\phi (X)^{-1}\phi (K)]$$ holds for a wider class of positive maps that is specified here. We also comment on the connections of this inequality with various monotonicity statements that have found wide use in mathematical physics, and apply it, and a close relative, to obtain some new, definitive results.more » « less
-
Let $$\phi(x,y)$$ be a continuous function, smooth away from the diagonal, such that, for some $$\alpha>0$$, the associated generalized Radon transforms \begin{equation} \label{Radon} R_t^{\phi}f(x)=\int_{\phi(x,y)=t} f(y) \psi(y) d\sigma_{x,t}(y) \end{equation} map $$L^2({\mathbb R}^d) \to H^{\alpha}({\mathbb R}^d)$$ for all $t>0$. Let $$E$$ be a compact subset of $${\mathbb R}^d$$ for some $$d \ge 2$$, and suppose that the Hausdorff dimension of $$E$$ is $$>d-\alpha$$. We show that any tree graph $$T$$ on $k+1$ ($$k \ge 1$$) vertices is realizable in $$E$$, in the sense that there exist distinct $$x^1, x^2, \dots, x^{k+1} \in E$$ and $t>0$ such that the $$\phi$$-distance $$\phi(x^i, x^j)$$ is equal to $$t$$ for all pairs $(i,j)$ corresponding to the edges of the graph $$T$$.more » « less
-
For domains in R d \mathbb {R}^d , d ≥ 2 d\geq 2 , we prove universal upper and lower bounds on the product of the bottom of the spectrum for the Laplacian to the power p > 0 p>0 and the supremum over all starting points of the p p -moments of the exit time of Brownian motion. It is shown that the lower bound is sharp for integer values of p p and that for p ≥ 1 p \geq 1 , the upper bound is asymptotically sharp as d → ∞ d\to \infty . For all p > 0 p>0 , we prove the existence of an extremal domain among the class of domains that are convex and symmetric with respect to all coordinate axes. For this class of domains we conjecture that the cube is extremal.more » « less
