اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدA Fast Max Flow Algorithm
372
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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 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 it
s 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.
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.
The wide applicability of kernels makes the problem of max-kernel search ubiquitous and more general than the usual similarity search in metric spaces. We focus on solving this problem efficiently. We begin by characterizing the inherent hardness of
the max-kernel search problem with a novel notion of directional concentration. Following that, we present a method to use an $O(n log n)$ algorithm to index any set of objects (points in $Real^dims$ or abstract objects) directly in the Hilbert space without any explicit feature representations of the objects in this space. We present the first provably $O(log n)$ algorithm for exact max-kernel search using this index. Empirical results for a variety of data sets as well as abstract objects demonstrate up to 4 orders of magnitude speedup in some cases. Extensions for approximate max-kernel search are also presented.
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$-se
quence, 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.
In 1969, Strassen shocked the world by showing that two n x n matrices could be multiplied in time asymptotically less than $O(n^3)$. While the recursive construction in his algorithm is very clear, the key gain was made by showing that 2 x 2 matrix
multiplication could be performed with only 7 multiplications instead of 8. The latter construction was arrived at by a process of elimination and appears to come out of thin air. Here, we give the simplest and most transparent proof of Strassens algorithm that we are aware of, using only a simple unitary 2-design and a few easy lines of calculation. Moreover, using basic facts from the representation theory of finite groups, we use 2-designs coming from group orbits to generalize our construction to all n (although the resulting algorithms arent optimal for n at least 3).
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
