The modularity is the best known and widely used quality function for community detection in graphs. We investigate the approximability of the modularity maximization problem and some related problems. We first design a polynomial-time 0.4209-additive approximation algorithm for the modularity maximization problem, which improves the current best additive approximation error of 0.4672. Our theoretical analysis also demonstrates that the proposed algorithm obtains a nearly-optimal solution for any instance with a high modularity value. We next design a polynomial-time 0.1660-additive approximation algorithm for the maximum modularity cut problem. Finally, we extend our algorithm to some related problems.

The Hitchcock transportation problem is a special case of the minimum cost flow problem where the graph is bipartite and capacities are infinite. If we let m denote the size of the larger and n the size of the smaller side of the bipartition, we call the Hitchcock transportation problem unbalanced if m is much larger than n. The unbalanced case arises in various applications, motivating the search for algorithms whose running time dependence on m is as small as possible. In this work, we give an algorithm with running time , which is the fastest known algorithm whose running time grows linearly in m. Moreover, we compare running times of algorithms for the Hitchcock transportation problem and the minimum cost flow problem and point out the fastest algorithms for particular relations of m and n, where m and n denote the number of edges and vertices in the context of the minimum cost flow problem. © 2015 Wiley Periodicals, Inc. NETWORKS, Vol. 67(2), 170–182 2016

One of the most promising techniques in the 14 nm logic node and beyond is triple patterning lithography (TPL). Recently, LELECUT type TPL technology, where the third mask is used to cut the patterns, is discussed to alleviate native conflict and overlay problems in LELELE type TPL. In this paper, we formulate LELECUT mask assignment problem which maximizes the compliance to the lithography and apply a positive semidefinite relaxation. In our proposed method, the positive semidefinite relaxation is defined by extracting cut candidates from the layout, and a mask assignment is obtained from an optimum solution of the relaxation by randomized rounding technique.

Abstract We consider the master ring problem (MRP) which often arises in optical network design. Given a network which consists of a collection of interconnected rings R1,…,RK, with n1,…,nK distinct nodes, respectively, we need to find an ordering of the nodes in the network that respects the ordering of every individual ring, if one exists. We show that MRP is NP‐complete, and therefore, it is unlikely to be solvable by a polynomial time algorithm. Our main result is an algorithm which solves MRP in $ Q \cdot \Pi_{k=1}^{K} (n_{k}/\sqrt{2}) $ steps, for some polynomial Q, as the nk values become large. For the ring clearance problem, a special case of practical interest, our algorithm achieves this running time for rings of any size nk ≥ 2. This yields the first nontrivial improvement, by factor of $ (2\sqrt{2})^{K} \approx (2.82)^{K} $ , over the running time of the naive algorithm, which exhaustively enumerates all $ \Pi_{k=1}^{K} (2n_{k}) $ possible solutions. © 2008 Wiley Periodicals, Inc. NETWORKS, 2008

In this paper, we propose the first fully polynomial-time randomized approximation scheme (FPRAS) for closed Jackson networks with single servers. Our algorithm is based on the Markov chain Monte Carlo (MCMC) method, and our scheme returns an approximate solution, for which the size of error satisfies a given error rate. We propose two Markov chains: one is for approximate sampling, and the other is for perfect sampling based on the monotone coupling from the past algorithm.

Abstract The Hungarian method is an efficient algorithm for finding a minimal‐cost perfect matching in a weighted bipartite graph. This paper describes an efficient algorithm for finding all minimal‐cost perfect matchings. The computational time required to generate each additional perfect matching is O(n(n + m)), and it requires O(n + m) memory storage. This problem can be solved by algorithms for finding the Kth‐best solution of assignment problems. However, the memory storage required by the known algorithms grows in proportion to K, and, hence, it may grow exponentially in n. So, our specialized algorithm has a considerable advantage in memory requirement over the precious more general algorithms for Kth‐best assignment problems. Here we will show that the enumeration of all minimal‐cost perfect matchings can be reduced to the enumeration of all perfect matchings in some bipartite graph. Therefore, our algorithm can be seen as an algorithm for enumerating all perfect matchings in a given bipartite graph.