Search

The terminal backup problems ([E. Anshelevich and A. Karagiozova, SIAM J. Comput., 40 (2011), pp. 678--708]) form a class of network design problems: Given an undirected graph with a requirement on terminals, the goal is to find a minimum-cost subgraph satisfying the connectivity requirement. The node-connectivity terminal backup problem requires a terminal to connect other terminals with a number of node-disjoint paths. This problem is not known whether is NP-hard or tractable. Fukunaga [SIAM J. Discrete Math., 30 (2016), pp. 777--800] gave a 4/3-approximation algorithm based on an LP-rounding scheme using a general LP-solver. In this paper, we develop a combinatorial algorithm for the relaxed LP to find a half-integral optimal solution in O(mlog(n-A · MF(/cn,m T/c2n)) time, where n is the number of nodes, m is the number of edges, k is the number of terminals, A is the maximum edge-cost, U is the maximum edge-capacity, and MF(nz,mz) is the time complexity of a max-flow algorithm in a network with nz nodes and m' edges. The algorithm implies that the 4/3-approximation algorithm for the node-connectivity terminal backup problem is also efficiently implemented. For the design of algorithm, we explore a connection between the node-connectivity terminal backup problem and a new type of a multiflow, which is called a separately capacitated multiflow. We show a min-max theorem which extends the Lovasz-Cherkassky theorem to the node-capacity setting. Our results build on discrete convexity in the node-connectivity terminal backup problem. [ABSTRACT FROM AUTHOR]

Submodularity is one of the most important properties in combinatorial optimization, and k-submodularity is a generalization of submodularity. Maximization of a k-submodular function requires an exponential number of value oracle queries, and approximation algorithms have been studied. For unconstrained k-submodular maximization, Iwata, Tanigawa, and Yoshida, [Improved approximation algorithms for k-submodular function maximization, in Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 2016, pp. 404-413] gave a randomized k/(2k 1)-approximation algorithm for monotone functions and a randomized 1/2-approximation algorithm for nonmonotone functions. In this paper, we present improved randomized algorithms for nonmonotone functions. Our algorithm gives a k2+1 2k2+1 -approximation for k geq 3. We also give a randomized surd 17 3 2 -approximation algorithm for k = 3. We use the same framework used in Iwata, Tanigawa, and Yoshida, [Improved approximation algorithms for k-submodular function maximization, in Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 2016, pp. 404--413] and Ward and v Zivn'y [ACM Trans. Algorithms, 12 (2016), pp. 46:1--47:26] with different probabilities. [ABSTRACT FROM AUTHOR]

We revisit the classic problem of estimating the moments of the degree distribution of an undirected simple graph. Consider an undirected simple graph G = (V,E) with n (nonisolated) vertices, and define (for s > 0) Ms =\sum v\in V ds v. Our aim is to estimate Ms within a multiplicative error of (1 +\varepsilon) (for a given approximation parameter\varepsilon > 0) in sublinear time. We consider the sparse-graph model that allows access to uniform random vertices, queries for the degree of any vertex, and queries for a neighbor of any vertex. For the case of s = 1 (the average degree), O\ast (\surd n) queries suffice for any constant\varepsilon [U. Feige, SIAM J. Comput., 35 (2006), pp. 964--984], [O. Goldreich and D. Ron, Random Structures Algorithms, 32 (2008), pp. 473--493]. (We use the O\ast notation to suppress dependencies in log n and 1/\varepsilon.) Gonen, Ron, and Shavitt [SIAM J. Discrete Math., 25 (2011), pp. 1365--1411] extended this result to all integral s > 0 by designing an algorithm that performs O\ast (n1 1/(s+1)) queries. (Strictly speaking, their algorithm approximates the number of star-subgraphs of a given size, but a slight modification gives an algorithm for moments.) We design a new, significantly simpler algorithm for this problem. In the worst case, it exactly matches the bounds of Gonen, Ron, and Shavitt and has a much simpler proof. More importantly, the running time of this algorithm is connected to the arboricity of G. This is (essentially) the maximum density of an induced subgraph. For the family of graphs with arboricity at most\alpha, it has a query complexity of O\ast\bigl(n\cdot\alpha 1/s M 1/s s + min\bigl\{ m M 1/s s, m\cdot ns 1 Ms\bigr\}\bigr) which is always upper bounded by O\ast\bigl(n\alpha M 1/s s\bigr). Thus, for the class of constant-arboricity graphs (which includes, among others, all minor-closed families and preferential attachment graphs), we can estimate the average degree in O\ast (1) queries, and we can estimate the variance of the degree distribution in O\ast (\surd n) queries. This is a major improvement over the previous worst-case bounds. [ABSTRACT FROM AUTHOR]