Search

A powerful technique for solving combinatorial optimization problems is to reduce the search space without compromising the solution quality by exploring intrinsic mathematical properties of the problems. For the maximum weight independent set (MWIS) problem, using an upper bound lemma which says the weight of any independent set not contained in the MWIS is bounded from above by the weight of the intersection of its closed neighbor set and the MWIS, we give two extension theorems -- independent set extension theorem and vertex cover extension theorem. With them at our disposal, two types of causal inference techniques (CITs) are proposed on the assumption that a vertex is strongly reducible (included or not included in all MWISs) or reducible (contained or not contained in a MWIS). One is a strongly reducible state-preserving technique, which extends a strongly reducible vertex into a vertex set where all vertices have the same strong reducibility. The other, as a reducible state-preserving technique, extends a reducible vertex into a vertex set with the same reducibility as that vertex and creates some weighted packing constraints to narrow the search space. Numerical experiments show that our CITs can help reduction algorithms find much smaller remaining graphs, improve the ability of exact algorithms to find the optimal solutions and help heuristic algorithms produce approximate solutions of better quality. In particular, detailed tests on $12$ representative graphs generated from datasets in Network Data Repository demonstrate that, compared to the state-of-the-art algorithms, the size of remaining graphs is further reduced by more than 32.6%, and the number of solvable instances is increased from 1 to 5., Comment: 31 pages, 5 figures, submitted for publication on Jan. 13, 2023

Capacity constrained optimal transport is a variant of optimal transport, which adds extra constraints on the set of feasible couplings in the original optimal transport problem to limit the mass transported between each pair of source and sink. Based on this setting, constrained optimal transport has numerous applications, e.g., finance, network flow. However, due to the large number of constraints in this problem, existing algorithms are both time-consuming and space-consuming. In this paper, inspired by entropic regularization for the classical optimal transport problem, we introduce a novel regularization term for capacity constrained optimal transport. The regularized problem naturally satisfies the capacity constraints and consequently makes it possible to analyze the duality. Unlike the matrix-vector multiplication in the alternate iteration scheme for solving classical optimal transport, in our algorithm, each alternate iteration step is to solve several single-variable equations. Fortunately, we find that each of these equations corresponds to a single-variable monotonic function, and we convert solving these equations into finding the unique zero point of each single-variable monotonic function with Newton's method. Extensive numerical experiments demonstrate that our proposed method has a significant advantage in terms of accuracy, efficiency, and memory consumption compared with existing methods., Comment: 17 pages, 3 figures

Many network applications can be formulated as NP-hard combinatorial optimization problems of community detection (CD). Due to the NP-hardness, to balance the CD quality and efficiency remains a challenge. Most existing CD methods are transductive, which are independently optimized only for the CD on a single graph. Some of these methods use advanced machine learning techniques to obtain high-quality CD results but usually have high complexity. Other approaches use fast heuristic approximation to ensure low runtime but may suffer from quality degradation. In contrast to these transductive methods, we propose an alternative inductive community detection (ICD) method across graphs of a system or scenario to alleviate the NP-hard challenge. ICD first conducts the offline training of an adversarial dual GNN on historical graphs to capture key properties of the system. The trained model is then directly generalized to new unseen graphs for online CD without additional optimization, where a better trade-off between quality and efficiency can be achieved. ICD can also capture the permutation invariant community labels in the offline training and tackle the online CD on new graphs with non-fixed number of nodes and communities. Experiments on a set of benchmarks demonstrate that ICD can achieve a significant trade-off between quality and efficiency over various baselines.

In order to increase the efficiency of phase retrieval,Wang proposed a high-speed moire phase retrieval method.But it is used only to measure the tiny object. In view of the limitation of Wang method,we proposed a dynamic three-dimensional (3D) measurement based on the phase-shifting moire algorithm.First, four sinusoidal fringe patterns with a pi/2 phase-shift are projected on the reference plane and acquired four deformed fringe patterns of the reference plane in advance. Then only single-shot deformed fringe pattern of the tested object is captured in measurement process.Four moire fringe patterns can be obtained by numerical multiplication between the the AC component of the object pattern and the AC components of the reference patterns respectively. The four low-frequency components corresponding to the moire fringe patterns are calculated by the complex encoding FT (Fourier transform) ,spectrum filtering and inverse FT.Thus the wrapped phase of the object can be determined in the tangent form from the four phase-shifting moire fringe patterns using the four-step phase shifting algorithm.The continuous phase distribution can be obtained by the conventional unwrapping algorithm. Finally, experiments were conducted to prove the validity and feasibility of the proposed method. The results are analyzed and compared with those of Wang method, demonstrating that our method not only can expand the measurement scope, but also can improve accuracy., 14 pages,5 figures. ams.org

We comment on the recent Letter by Xu and Wang et al. [Opt. Lett. 41, 2430 (2016)] in which an approach of quantitative phase extraction in dual-wavelength in-line phase-shifting interferometry (DWILPSI) was proposed. It is noted that a special phase shift is used, which more or less embarrasses its practical operation. We wish to show that the same result can also be reached by combining the generalized phase-shifting algorithm and the least-square algorithm, in which the phase shift can be chosen randomly. In addition to maintaining high accuracy and rapid processing speed of the DWILPSI method, the proposed method greatly facilitates its application in actual measurement.