In this paper, we consider the perfect demand matching problem (PDM) which combines aspects of the knapsack problem along with the b-matching problem. It is a generalization of the maximum weight matching problem whic...
详细信息
In this paper, we consider the perfect demand matching problem (PDM) which combines aspects of the knapsack problem along with the b-matching problem. It is a generalization of the maximum weight matching problem which has been fundamental in the development of theory of computer science and operations research. This problem is NP-hard and there exists a constant c > 0 such that the problem admits no 1 + c-approximation algorithm, unless P=NP. Here, we investigate the performance of a distributed message passing algorithm called Max-sum belief propagation for computing the problem of finding the optimal perfect demand matching. As the main result, we demonstrate the rigorous theoretical analysis of the Max-sum BP algorithm for PDM, and establish that within pseudo-polynomial-time, our algorithm could converge to the optimal solution of PDM, provided that the optimal solution of its LP relaxation is unique and integral. Different from the techniques used in previous literature, our analysis is based on primal-dual complementary slackness conditions, and thus the number of iterations of the algorithm is independent of the structure of the given graph. Moreover, to the best of our knowledge, this is one of a very few instances where BP algorithm is proved correct for NP-hard problems.(c) 2023 Elsevier Inc. All rights reserved.
We give the first fully dynamic algorithm which maintains a (1 - epsilon)-approximate densest subgraph in worst-case time poly(log n, epsilon(-1)) per update. Dense subgraph discovery is an important primitive for man...
详细信息
ISBN:
(纸本)9781450369794
We give the first fully dynamic algorithm which maintains a (1 - epsilon)-approximate densest subgraph in worst-case time poly(log n, epsilon(-1)) per update. Dense subgraph discovery is an important primitive for many real-world applications such as community detection, link spam detection, distance query indexing, and computational biology. We approach the densest subgraph problem by framing its dual as a graph orientation problem, which we solve using an augmenting path-like adjustment technique. Our result improves upon the previous best approximation factor of ( 1/4 - epsilon) for fully dynamic densest subgraph [Bhattacharya et. al., STOC '15]. We also extend our techniques to solving the problem on vertex-weighted graphs with similar runtimes. Additionally, we reduce the (1 - epsilon)-approximate densest subgraph problem on directed graphs to.. (log n/epsilon) instances of (1 - epsilon)-approximate densest subgraph on vertex-weighted graphs. This reduction, together with our algorithm for vertex-weighted graphs, gives the first fully-dynamic algorithm for directed densest subgraph in worst-case time poly( log n, epsilon(-1)) per update. Moreover, combined with a near-linear time algorithm for densest subgraph [Bahmani et. al., WAW'14], this gives the first near-linear time algorithm for directed densest subgraph.
暂无评论