We devise new cut sparsifiers that are related to the classical sparsification of Nagamochi and Ibaraki [Algorithmica, 1992], which is an algorithm that, given an unweighted graph $G$ on $n$ nodes and a parameter $k$, computes a subgraph with $O(nk)$ edges that preserves all cuts of value up to $k$. We put forward the notion of a friendly cut sparsifier, which is a minor of $G$ that preserves all friendly cuts of value up to $k$, where a cut in $G$ is called friendly if every node has more edges connecting it to its own side of the cut than to the other side. We present an algorithm that, given a simple graph $G$, computes in almost-linear time a friendly cut sparsifier with $\tilde{O}(n \sqrt{k})$ edges. Using similar techniques, we also show how, given in addition a terminal set $T$, one can compute in almost-linear time a terminal sparsifier, which preserves the minimum $st$-cut between every pair of terminals, with $\tilde{O}(n \sqrt{k} + |T| k)$ edges. Plugging these sparsifiers into the recent $n^{2+o(1)}$-time algorithms for constructing a Gomory-Hu tree of simple graphs, along with a relatively simple procedure for handling the unfriendly minimum cuts, we improve the running time for moderately dense graphs (e.g., with $m=n^{1.75}$ edges). In particular, assuming a linear-time Max-Flow algorithm, the new state-of-the-art for Gomory-Hu tree is the minimum between our $(m+n^{1.75})^{1+o(1)}$ and the known $m n^{1/2+o(1)}$. We further investigate the limits of this approach and the possibility of better sparsification. Under the hypothesis that an $\tilde{O}(n)$-edge sparsifier that preserves all friendly minimum $st$-cuts can be computed efficiently, our upper bound improves to $\tilde{O}(m+n^{1.5})$ which is the best possible without breaking the cubic barrier for constructing Gomory-Hu trees in non-simple graphs.
相關內容
We study joint unicast and multigroup multicast transmission in single-cell massive multiple-input-multiple-output (MIMO) systems, under maximum ratio transmission. For the unicast transmission, the objective is to maximize the weighted sum spectral efficiency (SE) of the unicast user terminals (UTs) and for the multicast transmission the objective is to maximize the minimum SE of the multicast UTs. These two problems are coupled to each other in a conflicting manner, due to their shared power resource and interference. To address this, we formulate a multiobjective optimization problem (MOOP). We derive the Pareto boundary of the MOOP analytically and determine the values of the system parameters to achieve any desired Pareto optimal point. Moreover, we prove that the Pareto region is convex, hence the system should serve the unicast and multicast UTs at the same time-frequency resource.
In this paper, we mainly study quaternary linear codes and their binary subfield codes. First we obtain a general explicit relationship between quaternary linear codes and their binary subfield codes in terms of generator matrices and defining sets. Second, we construct quaternary linear codes via simplicial complexes and determine the weight distributions of these codes. Third, the weight distributions of the binary subfield codes of these quaternary codes are also computed by employing the general characterization. Furthermore, we present two infinite families of optimal linear codes with respect to the Griesmer Bound, and a class of binary almost optimal codes with respect to the Sphere Packing Bound. We also need to emphasize that we obtain at least 9 new quaternary linear codes.
We study a multivariate version of trend filtering, called Kronecker trend filtering or KTF, for the case in which the design points form a lattice in $d$ dimensions. KTF is a natural extension of univariate trend filtering (Steidl et al., 2006; Kim et al., 2009; Tibshirani, 2014), and is defined by minimizing a penalized least squares problem whose penalty term sums the absolute (higher-order) differences of the parameter to be estimated along each of the coordinate directions. The corresponding penalty operator can be written in terms of Kronecker products of univariate trend filtering penalty operators, hence the name Kronecker trend filtering. Equivalently, one can view KTF in terms of an $\ell_1$-penalized basis regression problem where the basis functions are tensor products of falling factorial functions, a piecewise polynomial (discrete spline) basis that underlies univariate trend filtering. This paper is a unification and extension of the results in Sadhanala et al. (2016, 2017). We develop a complete set of theoretical results that describe the behavior of $k^{\mathrm{th}}$ order Kronecker trend filtering in $d$ dimensions, for every $k \geq 0$ and $d \geq 1$. This reveals a number of interesting phenomena, including the dominance of KTF over linear smoothers in estimating heterogeneously smooth functions, and a phase transition at $d=2(k+1)$, a boundary past which (on the high dimension-to-smoothness side) linear smoothers fail to be consistent entirely. We also leverage recent results on discrete splines from Tibshirani (2020), in particular, discrete spline interpolation results that enable us to extend the KTF estimate to any off-lattice location in constant-time (independent of the size of the lattice $n$).
In 1943, Hadwiger conjectured that every graph with no $K_t$ minor is $(t-1)$-colorable for every $t\ge 1$. In the 1980s, Kostochka and Thomason independently proved that every graph with no $K_t$ minor has average degree $O(t\sqrt{\log t})$ and hence is $O(t\sqrt{\log t})$-colorable. Recently, Norin, Song and the second author showed that every graph with no $K_t$ minor is $O(t(\log t)^{\beta})$-colorable for every $\beta > 1/4$, making the first improvement on the order of magnitude of the $O(t\sqrt{\log t})$ bound. The first main result of this paper is that every graph with no $K_t$ minor is $O(t\log\log t)$-colorable. This is a corollary of our main technical result that the chromatic number of a $K_t$-minor-free graph is bounded by $O(t(1+f(G,t)))$ where $f(G,t)$ is the maximum of $\frac{\chi(H)}{a}$ over all $a\ge \frac{t}{\sqrt{\log t}}$ and $K_a$-minor-free subgraphs $H$ of $G$ that are small (i.e. $O(a\log^4 a)$ vertices). This has a number of interesting corollaries. First as mentioned, using the current best-known bounds on coloring small $K_t$-minor-free graphs, we show that $K_t$-minor-free graphs are $O(t\log\log t)$-colorable. Second, it shows that proving Linear Hadwiger's Conjecture (that $K_t$-minor-free graphs are $O(t)$-colorable) reduces to proving it for small graphs. Third, we prove that $K_t$-minor-free graphs with clique number at most $\sqrt{\log t}/ (\log \log t)^2$ are $O(t)$-colorable. This implies our final corollary that Linear Hadwiger's Conjecture holds for $K_r$-free graphs for every fixed $r$. One key to proving the main theorem is a new standalone result that every $K_t$-minor-free graph of average degree $d=\Omega(t)$ has a subgraph on $O(t \log^3 t)$ vertices with average degree $\Omega(d)$.
Mining maximal subgraphs with cohesive structures from a bipartite graph has been widely studied. One important cohesive structure on bipartite graphs is k-biplex, where each vertex on one side disconnects at most k vertices on the other side. In this paper, we study the maximal k-biplex enumeration problem which enumerates all maximal k-biplexes. Existing methods suffer from efficiency and/or scalability issues and have the time of waiting for the next output exponential w.r.t. the size of the input bipartite graph (i.e., an exponential delay). In this paper, we adopt a reverse search framework called bTraversal, which corresponds to a depth-first search (DFS) procedure on an implicit solution graph on top of all maximal k-biplexes. We then develop a series of techniques for improving and implementing this framework including (1) carefully selecting an initial solution to start DFS, (2) pruning the vast majority of links from the solution graph of bTraversal, and (3) implementing abstract procedures of the framework. The resulting algorithm is called iTraversal, which has its underlying solution graph significantly sparser than (around 0.1% of) that of bTraversal. Besides, iTraversal provides a guarantee of polynomial delay. Our experimental results on real and synthetic graphs, where the largest one contains more than one billion edges, show that our algorithm is up to four orders of magnitude faster than existing algorithms.
We investigate online convex optimization in non-stationary environments and choose the \emph{dynamic regret} as the performance measure, defined as the difference between cumulative loss incurred by the online algorithm and that of any feasible comparator sequence. Let $T$ be the time horizon and $P_T$ be the path-length that essentially reflects the non-stationarity of environments, the state-of-the-art dynamic regret is $\mathcal{O}(\sqrt{T(1+P_T)})$. Although this bound is proved to be minimax optimal for convex functions, in this paper, we demonstrate that it is possible to further enhance the guarantee for some easy problem instances, particularly when online functions are smooth. Specifically, we propose novel online algorithms that can leverage smoothness and replace the dependence on $T$ in the dynamic regret by \emph{problem-dependent} quantities: the variation in gradients of loss functions, the cumulative loss of the comparator sequence, and the minimum of the previous two terms. These quantities are at most $\mathcal{O}(T)$ while could be much smaller in benign environments. Therefore, our results are adaptive to the intrinsic difficulty of the problem, since the bounds are tighter than existing results for easy problems and meanwhile guarantee the same rate in the worst case. Notably, our algorithm requires only \emph{one} gradient per iteration, which shares the same gradient query complexity with the methods developed for optimizing the static regret. As a further application, we extend the results from the full-information setting to bandit convex optimization with two-point feedback and thereby attain the first problem-dependent dynamic regret for such bandit tasks.
The one-fifth success rule is one of the best-known and most widely accepted techniques to control the parameters of evolutionary algorithms. While it is often applied in the literal sense, a common interpretation sees the one-fifth success rule as a family of success-based updated rules that are determined by an update strength $F$ and a success rate. We analyze in this work how the performance of the (1+1) Evolutionary Algorithm on LeadingOnes depends on these two hyper-parameters. Our main result shows that the best performance is obtained for small update strengths $F=1+o(1)$ and success rate $1/e$. We also prove that the running time obtained by this parameter setting is, apart from lower order terms, the same that is achieved with the best fitness-dependent mutation rate. We show similar results for the resampling variant of the (1+1) Evolutionary Algorithm, which enforces to flip at least one bit per iteration.
Aiming to recover the data from several concurrent node failures, linear $r$-LRC codes with locality $r$ were extended into $(r, \delta)$-LRC codes with locality $(r, \delta)$ which can enable the local recovery of a failed node in case of more than one node failure. Optimal LRC codes are those whose parameters achieve the generalized Singleton bound with equality. In the present paper, we are interested in studying optimal LRC codes over small fields and, more precisely, over $\mathbb{F}_4$. We shall adopt an approach by investigating optimal quaternary $(r,\delta)$-LRC codes through their parity-check matrices. Our study includes determining the structural properties of optimal $(r,\delta)$-LRC codes, their constructions, and their complete classification over $\F_4$ by browsing all possible parameters. We emphasize that the precise structure of optimal quaternary $(r,\delta)$-LRC codes and their classification are obtained via the parity-check matrix approach use proofs-techniques different from those used recently for optimal binary and ternary $(r,\delta)$-LRC codes obtained by Hao et al. in [IEEE Trans. Inf. Theory, 2020, 66(12): 7465-7474].
Motivated by many interesting real-world applications in logistics and online advertising, we consider an online allocation problem subject to lower and upper resource constraints, where the requests arrive sequentially, sampled i.i.d. from an unknown distribution, and we need to promptly make a decision given limited resources and lower bounds requirements. First, with knowledge of the measure of feasibility, i.e., $\alpha$, we propose a new algorithm that obtains $1-O(\frac{\epsilon}{\alpha-\epsilon})$ -competitive ratio for the offline problems that know the entire requests ahead of time. Inspired by the previous studies, this algorithm adopts an innovative technique to dynamically update a threshold price vector for making decisions. Moreover, an optimization method to estimate the optimal measure of feasibility is proposed with theoretical guarantee at the end of this paper. Based on this method, if we tolerate slight violation of the lower bounds constraints with parameter $\eta$, the proposed algorithm is naturally extended to the settings without strong feasible assumption, which cover the significantly unexplored infeasible scenarios.
We present a randomized $O(m \log^2 n)$ work, $O(\text{polylog } n)$ depth parallel algorithm for minimum cut. This algorithm matches the work bounds of a recent sequential algorithm by Gawrychowski, Mozes, and Weimann [ICALP'20], and improves on the previously best parallel algorithm by Geissmann and Gianinazzi [SPAA'18], which performs $O(m \log^4 n)$ work in $O(\text{polylog } n)$ depth. Our algorithm makes use of three components that might be of independent interest. Firstly, we design a parallel data structure that efficiently supports batched mixed queries and updates on trees. It generalizes and improves the work bounds of a previous data structure of Geissmann and Gianinazzi and is work efficient with respect to the best sequential algorithm. Secondly, we design a parallel algorithm for approximate minimum cut that improves on previous results by Karger and Motwani. We use this algorithm to give a work-efficient procedure to produce a tree packing, as in Karger's sequential algorithm for minimum cuts. Lastly, we design an efficient parallel algorithm for solving the minimum $2$-respecting cut problem.
小貼士
登錄享
相關主題
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191