Abstract We consider a two-stage submodular maximization problem subject to a cardinality constraint and k matroid constraints, where the objective function is the expected difference of a nonnegative monotone submodular function and a nonnegative monotone modular function. We give two bi-factor approximation algorithms for this problem. The first is a deterministic $\left( {{1 \over {k + 1}}\left( {1 - {1 \over {{e^{k + 1}}}}} \right),1} \right)$ -approximation algorithm, and the second is a randomized $\left( {{1 \over {k + 1}}\left( {1 - {1 \over {{e^{k + 1}}}}} \right) - \varepsilon ,1} \right)$ -approximation algorithm with improved time efficiency.

Abstract In the k-means problem with penalties, we are given a data set $${\cal D} \subseteq \mathbb{R}^\ell $$ of n points where each point $$j \in {\cal D}$$ is associated with a penalty cost pj and an integer k. The goal is to choose a set $${\rm{C}}S \subseteq {{\cal R}^\ell }$$ with |CS| ≤ k and a penalized subset $${{\cal D}_p} \subseteq {\cal D}$$ to minimize the sum of the total squared distance from the points in D / Dp to CS and the total penalty cost of points in Dp, namely $$\sum\nolimits_{j \in {\cal D}\backslash {{\cal D}_p}} {d^2}(j,{\rm{C}}S) + \sum\nolimits_{j \in {{\cal D}_p}} {p_j}$$ . We employ the primal-dual technique to give a pseudo-polynomial time algorithm with an approximation ratio of (6.357+ε) for the k-means problem with penalties, improving the previous best approximation ratio 19.849+∊ for this problem given by Feng et al. in Proceedings of FAW (2019).

Sentiment classification has received much attention in both engineering and academic fields. Deep belief networks (DBN) has proved powerful in many domains including natural language processing. In this paper, DBN is applied in sentiment classification, while we propose a new way to improve the DBN based on the unsupervised training phase of restricted Boltzmann machines (RBM). That is, the RBM generates the hidden layer in an unsupervised fashion, and then we use this hidden layer as the output of a single-layer neural network, which is trained using the delta rule. The new weights trained from delta rule are then transmitted into the whole back propagation. This way keeps much more correction signal information for each layer in back propagation compared to that in the same network structure. Consequently, our experimental results demonstrate that the new learning method performs relatively better on ten sentiment datasets, which further proves the delta rule improves DBN performance for natural language processing tasks.

Given an integer, nonnegative, symmetric matrix $R = (r_{ij})_{n \times n}$, we consider the problem of synthesizing an undirected network G on node set $V = \{1,2,\dots,n\}$ with nonnegative, integer edge capacities such that (i) for any pair $\{i,j\}$ of distinct nodes in V, the value of maximum flow between i and j in G equals exactly $r_{ij}$ and (ii) the sum of capacities of edges in G is minimum. Chou and Frank [IEEE Trans. Circuit Theory, CT-17 (1970), pp. 192–197] claim to give an algorithm for this problem. But, Schrijver [Algorithms Combin. 24, Springer-Verlag, Berlin, 2003, pp. 1049–1057] gives a counter-example to their claim. We present an $O(n^2)$ algorithm for the problem.

Abstract The maximum residual flow problem with one‐arc destruction is shown to be solvable in strongly polynomial time in [Aneja et al., Networks, 38 (2001), 194–198]. However, the status of the corresponding problem with more than one‐arc destruction is left open therein. We resolve the status of the two‐arc destruction problem by demonstrating that it is already NP‐hard. © 2007 Wiley Periodicals, Inc. NETWORKS, Vol. 50(3), 181–182 2007

Abstract We are given a directed network G = (V,A,u) with vertex set V, arc set A, a source vertex s ∈ V, a destination vertex t ∈ V, a finite capacity vector u = {uij}(i,j)∈A, and a positive integer m ∈ Z+. The multiroute maximum flow problem (m‐MFP) generalizes the ordinary maximum flow problem by seeking a maximum flow from s to t subject to not only the regular flow conservation constraints at the vertices (except s and t) and the flow capacity constraints at the arcs, but also the extra constraints that any flow must be routed along m arc‐disjoint s‐t paths. In this article, we devise two new combinatorial algorithms for m‐MFP. One is based on Newton's method and another is based on an augmenting‐path technique. We also show how the Newton‐based algorithm unifies two existing algorithms, and how the augmenting‐path algorithm is strongly polynomial for case m = 2. © 2006 Wiley Periodicals, Inc. NETWORKS, Vol. 47(2), 81–92 2006