ﻻ يوجد ملخص باللغة العربية
We present faster high-accuracy algorithms for computing $ell_p$-norm minimizing flows. On a graph with $m$ edges, our algorithm can compute a $(1+1/text{poly}(m))$-approximate unweighted $ell_p$-norm minimizing flow with $pm^{1+frac{1}{p-1}+o(1)}$ operations, for any $p ge 2,$ giving the best bound for all $pgtrsim 5.24.$ Combined with the algorithm from the work of Adil et al. (SODA 19), we can now compute such flows for any $2le ple m^{o(1)}$ in time at most $O(m^{1.24}).$ In comparison, the previous best running time was $Omega(m^{1.33})$ for large constant $p.$ For $psimdelta^{-1}log m,$ our algorithm computes a $(1+delta)$-approximate maximum flow on undirected graphs using $m^{1+o(1)}delta^{-1}$ operations, matching the current best bound, albeit only for unit-capacity graphs. We also give an algorithm for solving general $ell_{p}$-norm regression problems for large $p.$ Our algorithm makes $pm^{frac{1}{3}+o(1)}log^2(1/varepsilon)$ calls to a linear solver. This gives the first high-accuracy algorithm for computing weighted $ell_{p}$-norm minimizing flows that runs in time $o(m^{1.5})$ for some $p=m^{Omega(1)}.$ Our key technical contribution is to show that smoothed $ell_p$-norm problems introduced by Adil et al., are interreducible for different values of $p.$ No such reduction is known for standard $ell_p$-norm problems.
We give improved algorithms for the $ell_{p}$-regression problem, $min_{x} |x|_{p}$ such that $A x=b,$ for all $p in (1,2) cup (2,infty).$ Our algorithms obtain a high accuracy solution in $tilde{O}_{p}(m^{frac{|p-2|}{2p + |p-2|}}) le tilde{O}_{p}(m^
We study the problem of finding flows in undirected graphs so as to minimize the weighted $p$-norm of the flow for any $p > 1$. When $p=2$, the problem is that of finding an electrical flow, and its dual is equivalent to solving a Laplacian linear sy
$ $In many optimization problems, a feasible solution induces a multi-dimensional cost vector. For example, in load-balancing a schedule induces a load vector across the machines. In $k$-clustering, opening $k$ facilities induces an assignment cost v
The accuracy of quantum dynamics simulation is usually measured by the error of the unitary evolution operator in the operator norm, which in turn depends on certain norm of the Hamiltonian. For unbounded operators, after suitable discretization, the
Linear regression in $ell_p$-norm is a canonical optimization problem that arises in several applications, including sparse recovery, semi-supervised learning, and signal processing. Generic convex optimization algorithms for solving $ell_p$-regressi