Semi-online scheduling on two uniform machines with the known largest size

This paper investigates semi-online scheduling on two uniform machines with the known largest size. Denote by s _j the speed of each machine, j=1,2. Assume 0<s ₁≤s ₂, and let s=s ₂/s ₁ be the speed ratio. First, for the speed ratio \(s\in [1,\sqrt{2}]\), we present an optimal semi-online algorithm \(\mathcal{LSMP}\) with the competitive ratio \(\mathrm{max}\{\frac {2(s+1)}{2s+1},s\}\). Second, we present a semi-online algorithm \(\mathcal{HSMP}\). And for \(s\in(\sqrt{2},1+\sqrt{3})\), the competitive ratio of \(\mathcal{HSMP}\) is strictly smaller than that of the online algorithm \(\mathcal{LS}\). Finally, for the speed ratio s≥s ^*≈3.715, we show that the known largest size cannot help us to design a semi-online algorithm with the competitive ratio strictly smaller than that of \(\mathcal{LS}\). Moreover, we show a lower bound for \(s\in(\sqrt{2},s^{*})\).     

Total completion time minimization in online hierarchical scheduling of unit-size jobs

This paper investigates an online hierarchical scheduling problem on m parallel identical machines. Our goal is to minimize the total completion time of all jobs. Each job has a unit processing time and a hierarchy. The job with a lower hierarchy can only be processed on the first machine and the job with a higher hierarchy can be processed on any one of m machines. We first show that the lower bound of this problem is at least \(1+\min \{\frac{1}{m}, \max \{\frac{2}{\lceil x\rceil +\frac{x}{\lceil x\rceil }+3}, \frac{2}{\lfloor x\rfloor +\frac{x}{\lfloor x\rfloor }+3}\}\), where \(x=\sqrt{2m+4}\). We then present a greedy algorithm with tight competitive ratio of \(1+\frac{2(m-1)}{m(\sqrt{4m-3}+1)}\). The competitive ratio is obtained in a way of analyzing the structure of the instance in the worst case, which is different from the most common method of competitive analysis. In particular, when \(m=2\), we propose an optimal online algorithm with competitive ratio of \(16\) \(/\) \(13\), which complements the previous result which provided an asymptotically optimal algorithm with competitive ratio of 1.1573 for the case where the number of jobs n is infinite, i.e., \(n\rightarrow \infty \).     

Upper bounds for the total rainbow connection of graphs

A two-agent scheduling problem on parallel machines is considered. Our objective is to minimize the makespan for agent A, subject to an upper bound on the makespan for agent B. When the number of machines, denoted by \(m\), is chosen arbitrarily, we provide an \(O(n)\) algorithm with performance ratio \(2-\frac{1}{m}\), i.e., the makespan for agent A given by the algorithm is no more than \(2-\frac{1}{m}\) times the optimal value, while the makespan for agent B is no more than \(2-\frac{1}{m}\) times the threshold value. This ratio is proved to be tight. Moreover, when \(m=2\), we present an \(O(nlogn)\) algorithm with performance ratio \(\frac{1+\sqrt{17}}{4}\approx 1.28\) which is smaller than \(\frac{3}{2}\). The ratio is weakly tight.     

On judicious partitions of graphs

Let \(k, m\) be positive integers, let \(G\) be a graph with \(m\) edges, and let \(h(m)=\sqrt{2m+\frac{1}{4}}-\frac{1}{2}\). Bollobás and Scott asked whether \(G\) admits a \(k\)-partition \(V_{1}, V_{2}, \ldots , V_{k}\) such that \(\max _{1\le i\le k} \{e(V_{i})\}\le \frac{m}{k^2}+\frac{k-1}{2k^2}h(m)\) and \(e(V_1, \ldots , V_k)\ge {k-1\over k} m +{k-1\over 2k}h(m) -\frac{(k-2)^{2}}{8k}\). In this paper, we present a positive answer to this problem on the graphs with large number of edges and small number of vertices with degrees being multiples of \(k\). Particularly, if \(d\) is not a multiple of \(k\) and \(G\) is \(d\)-regular with \(m\ge {9\over 128}k^4(k-2)^2\), then \(G\) admits a \(k\)-partition as desired. We also improve an earlier result by showing that \(G\) admits a partition \(V_{1}, V_{2}, \ldots , V_{k}\) such that \(e(V_{1},V_{2},\ldots ,V_{k})\ge \frac{k-1}{k}m+\frac{k-1}{2k}h(m)-\frac{(k-2)^{2}}{2(k-1)}\) and \(\max _{1\le i\le k}\{e(V_{i})\}\le \frac{m}{k^{2}}+\frac{k-1}{2k^{2}}h(m)\).     

Online tradeoff scheduling on a single machine to minimize makespan and maximum lateness

In this paper, we consider the following single machine online tradeoff scheduling problem. A set of n independent jobs arrive online over time. Each job \(J_{j}\) has a release date \(r_{j}\), a processing time \(p_{j}\) and a delivery time \(q_{j}\). The characteristics of a job are unknown until it arrives. The goal is to find a schedule that minimizes the makespan \(C_{\max } = \max _{1 \le j \le n} C_{j}\) and the maximum lateness \(L_{\max } = \max _{1 \le j \le n} L_{j}\), where \(L_{j} = C_{j} + q_{j}\). For the problem, we present a nondominated \(( \rho , 1 + \displaystyle \frac{1}{\rho } )\)-competitive online algorithm for each \(\rho \) with \( 1 \le \rho \le \displaystyle \frac{\sqrt{5} + 1}{2}\).     

Paired-domination number of claw-free odd-regular graphs

A paired-dominating set of a graph G is a dominating set of vertices whose induced subgraph has a perfect matching, while the paired-domination number is the minimum cardinality of a paired-dominating set in the graph, denoted by \(\gamma _{pr}(G)\). Let G be a connected \(\{K_{1,3}, K_{4}-e\}\)-free cubic graph of order n. We show that \(\gamma _{pr}(G)\le \frac{10n+6}{27}\) if G is \(C_{4}\)-free and that \(\gamma _{pr}(G)\le \frac{n}{3}+\frac{n+6}{9(\lceil \frac{3}{4}(g_o+1)\rceil +1)}\) if G is \(\{C_{4}, C_{6}, C_{10}, \ldots , C_{2g_o}\}\)-free for an odd integer \(g_o\ge 3\); the extremal graphs are characterized; we also show that if G is a 2 -connected, \(\gamma _{pr}(G) = \frac{n}{3} \). Furthermore, if G is a connected \((2k+1)\)-regular \(\{K_{1,3}, K_4-e\}\)-free graph of order n, then \(\gamma _{pr}(G)\le \frac{n}{k+1} \), with equality if and only if \(G=L(F)\), where \(F\cong K_{1, 2k+2}\), or k is even and \(F\cong K_{k+1,k+2}\).     

Nordhaus–Gaddum type result for the matching number of a graph

For a graph G, \(\alpha '(G)\) is the matching number of G. Let \(k\ge 2\) be an integer, \(K_{n}\) be the complete graph of order n. Assume that \(G_{1}, G_{2}, \ldots , G_{k}\) is a k-decomposition of \(K_{n}\). In this paper, we show that (1)

$$\begin{aligned} \left\lfloor \frac{n}{2}\right\rfloor \le \sum _{i=1}^{k} \alpha '(G_{i})\le k\left\lfloor \frac{n}{2}\right\rfloor . \end{aligned}$$

(2) If each \(G_{i}\) is non-empty for \(i = 1, \ldots , k\), then for \(n\ge 6k\),

$$\begin{aligned} \sum _{i=1}^{k} \alpha '(G_{i})\ge \left\lfloor \frac{n+k-1}{2}\right\rfloor . \end{aligned}$$

(3) If \(G_{i}\) has no isolated vertices for \(i = 1, \ldots , k\), then for \(n\ge 8k\),

$$\begin{aligned} \sum _{i=1}^{k} \alpha '(G_{i})\ge \left\lfloor \frac{n}{2}\right\rfloor +k. \end{aligned}$$

The bounds in (1), (2) and (3) are sharp. (4) When \(k= 2\), we characterize all the extremal graphs which attain the lower bounds in (1), (2) and (3), respectively.

     

Approximation for maximizing monotone non-decreasing set functions with a greedy method

We study the problem of maximizing a monotone non-decreasing function \(f\) subject to a matroid constraint. Fisher, Nemhauser and Wolsey have shown that, if \(f\) is submodular, the greedy algorithm will find a solution with value at least \(\frac{1}{2}\) of the optimal value under a general matroid constraint and at least \(1-\frac{1}{e}\) of the optimal value under a uniform matroid \((\mathcal {M} = (X,\mathcal {I})\), \(\mathcal {I} = \{ S \subseteq X: |S| \le k\}\)) constraint. In this paper, we show that the greedy algorithm can find a solution with value at least \(\frac{1}{1+\mu }\) of the optimum value for a general monotone non-decreasing function with a general matroid constraint, where \(\mu = \alpha \), if \(0 \le \alpha \le 1\); \(\mu = \frac{\alpha ^K(1-\alpha ^K)}{K(1-\alpha )}\) if \(\alpha > 1\); here \(\alpha \) is a constant representing the “elemental curvature” of \(f\), and \(K\) is the cardinality of the largest maximal independent sets. We also show that the greedy algorithm can achieve a \(1 - (\frac{\alpha + \cdots + \alpha ^{k-1}}{1+\alpha + \cdots + \alpha ^{k-1}})^k\) approximation under a uniform matroid constraint. Under this unified \(\alpha \)-classification, submodular functions arise as the special case \(0 \le \alpha \le 1\).     

On minimally 2-connected graphs with generalized connectivity $$\kappa _{3}=2$$

For \(S\subseteq G\), let \(\kappa (S)\) denote the maximum number r of edge-disjoint trees \(T_1, T_2, \ldots , T_r\) in G such that \(V(T_i)\cap V(T_j)=S\) for any \(i,j\in \{1,2,\ldots ,r\}\) and \(i\ne j\). For every \(2\le k\le n\), the k-connectivity of G, denoted by \(\kappa _k(G)\), is defined as \(\kappa _k(G)=\hbox {min}\{\kappa (S)| S\subseteq V(G)\ and\ |S|=k\}\). Clearly, \(\kappa _2(G)\) corresponds to the traditional connectivity of G. In this paper, we focus on the structure of minimally 2-connected graphs with \(\kappa _{3}=2\). Denote by \(\mathcal {H}\) the set of minimally 2-connected graphs with \(\kappa _{3}=2\). Let \(\mathcal {B}\subseteq \mathcal {H}\) and every graph in \(\mathcal {B}\) is either \(K_{2,3}\) or the graph obtained by subdividing each edge of a triangle-free 3-connected graph. We obtain that \(H\in \mathcal {H}\) if and only if \(H\in \mathcal {B}\) or H can be constructed from one or some graphs \(H_{1},\ldots ,H_{k}\) in \(\mathcal {B}\) (\(k\ge 1\)) by applying some operations recursively.     

Improved upper bound for the degenerate and star chromatic numbers of graphs

Let \(G=G(V,E)\) be a graph. A proper coloring of G is a function \(f:V\rightarrow N\) such that \(f(x)\ne f(y)\) for every edge \(xy\in E\). A proper coloring of a graph G such that for every \(k\ge 1\), the union of any k color classes induces a \((k-1)\)-degenerate subgraph is called a degenerate coloring; a proper coloring of a graph with no two-colored \(P_{4}\) is called a star coloring. If a coloring is both degenerate and star, then we call it a degenerate star coloring of graph. The corresponding chromatic number is denoted as \(\chi _{sd}(G)\). In this paper, we employ entropy compression method to obtain a new upper bound \(\chi _{sd}(G)\le \lceil \frac{19}{6}\Delta ^{\frac{3}{2}}+5\Delta \rceil \) for general graph G.     

Parameterized algorithms for min–max 2-cluster editing

For a given graph and an integer t, the Min–Max 2-Clustering problem asks if there exists a modification of a given graph into two maximal disjoint cliques by inserting or deleting edges such that the number of the editing edges incident to each vertex is at most t. It has been shown that the problem can be solved in polynomial time for \(t<n/4\), where n is the number of vertices. In this paper, we design parameterized algorithms for different ranges of t. Let \(k=t-n/4\). We show that the problem is polynomial-time solvable when roughly \(k<\sqrt{n/32}\). When \(k\in o(n)\), we design a randomized and a deterministic algorithm with sub-exponential time parameterized complexity, i.e., the problem is in SUBEPT. We also show that the problem can be solved in \(O({2}^{n/r}\cdot n^2)\) time for \(k<n/12\) and in \(O(n^2\cdot 2^{3n/4+k})\) time for \(n/12\le k< n/4\), where \(r=2+\lfloor (n/4-3k-2)/(2k+1) \rfloor \ge 2\).     

Online covering salesman problem

Given a graph \(G=(V,E,D,W)\), the generalized covering salesman problem (CSP) is to find a shortest tour in G such that each vertex \(i\in D\) is either on the tour or within a predetermined distance L to an arbitrary vertex \(j\in W\) on the tour, where \(D\subset V\),\(W\subset V\). In this paper, we propose the online CSP, where the salesman will encounter at most k blocked edges during the traversal. The edge blockages are real-time, meaning that the salesman knows about a blocked edge when it occurs. We present a lower bound \(\frac{1}{1 + (k + 2)L}k+1\) and a CoverTreeTraversal algorithm for online CSP which is proved to be \(k+\alpha \)-competitive, where \(\alpha =0.5+\frac{(4k+2)L}{OPT}+2\gamma \rho \), \(\gamma \) is the approximation ratio for Steiner tree problem and \(\rho \) is the maximal number of locations that a customer can be served. When \(\frac{L}{\texttt {OPT}}\rightarrow 0\), our algorithm is near optimal. The problem is also extended to the version with service cost, and similar results are derived.     

Total and forcing total edge-to-vertex monophonic number of a graph

For a connected graph \(G = \left( V,E\right) \), a set \(S\subseteq E(G)\) is called a total edge-to-vertex monophonic set of a connected graph G if the subgraph induced by S has no isolated edges. The total edge-to-vertex monophonic number \(m_{tev}(G)\) of G is the minimum cardinality of its total edge-to-vertex monophonic set of G. The total edge-to-vertex monophonic number of certain classes of graphs is determined and some of its general properties are studied. Connected graphs of size \(q \ge 3 \) with total edge-to-vertex monophonic number q is characterized. It is shown that for positive integers \(r_{m},d_{m}\) and \(l\ge 4\) with \(r_{m}< d_{m} \le 2 r_{m}\), there exists a connected graph G with \(\textit{rad}_ {m} G = r_{m}\), \(\textit{diam}_ {m} G = d_{m}\) and \(m_{tev}(G) = l\) and also shown that for every integers a and b with \(2 \le a \le b\), there exists a connected graph G such that \( m_{ev}\left( G\right) = b\) and \(m_{tev}(G) = a + b\). A forcing subset for S of minimum cardinality is a minimum forcing subset of S. The forcing total edge-to-vertex monophonic number of S, denoted by \(f_{tev}(S)\) is the cardinality of a minimum forcing subset of S. The forcing total edge-to-vertex monophonic number of G, denoted by \(f_{tev}(G) = \textit{min}\{f_{tev}(S)\}\), where the minimum is taken over all total edge-to-vertex monophonic set S in G. The forcing total edge-to-vertex monophonic number of certain classes of graphs are determined and some of its general properties are studied. It is shown that for every integers a and b with \(0 \le a \le b\) and \(b \ge 2\), there exists a connected graph G such that \(f_{tev}(G) = a\) and \( m _{tev}(G) = b\), where \( f _{tev}(G)\) is the forcing total edge-to-vertex monophonic number of G.     

A practical greedy approximation for the directed Steiner tree problem

The directed Steiner tree (DST) NP-hard problem asks, considering a directed weighted graph with n nodes and m arcs, a node r called root and a set of k nodes X called terminals, for a minimum cost directed tree rooted at r spanning X. The best known polynomial approximation ratio for DST is a \(O(k^\varepsilon )\)-approximation greedy algorithm. However, a much faster k-approximation, returning the shortest paths from r to X, is generally used in practice. We give two new algorithms : a fast k-approximation called Greedy\(_\text {FLAC}\) running in \(O(m \log (n)k + \min (m, nk)nk^2)\) and a \(O(\sqrt{k})\)-approximation called Greedy\(_\text {FLAC}^\triangleright \) running in \(O(nm + n^2 \log (n)k +n^2 k^3)\). We provide computational results to show that, Greedy\(_\text {FLAC}\) rivals in practice with the running time of the fast k-approximation and returns solution with smaller cost in practice.     

An upper bound on the double Roman domination number

A double Roman dominating function (DRDF) on a graph \(G=(V,E)\) is a function \(f : V \rightarrow \{0, 1, 2, 3\}\) having the property that if \(f(v) = 0\), then vertex v must have at least two neighbors assigned 2 under f or one neighbor w with \(f(w)=3\), and if \(f(v)=1\), then vertex v must have at least one neighbor w with \(f(w)\ge 2\). The weight of a DRDF f is the value \(f(V) = \sum _{u \in V}f(u)\). The double Roman domination number \(\gamma _{dR}(G)\) of a graph G is the minimum weight of a DRDF on G. Beeler et al. (Discrete Appl Math 211:23–29, 2016) observed that every connected graph G having minimum degree at least two satisfies the inequality \(\gamma _{dR}(G)\le \frac{6n}{5}\) and posed the question whether this bound can be improved. In this paper, we settle the question and prove that for any connected graph G of order n with minimum degree at least two, \(\gamma _{dR}(G)\le \frac{8n}{7}\).     

Cost sharing on prices for games on graphs

Let \(N=\{1,\dots ,n\}\) be a set of customers who want to buy a single homogenous goods in market. Let \(q_i>0\) be the quantity that \(i\in N\) demands, \(q=(q_1,\dots ,q_n)\) and \(q_S=\sum _{i\in S}q_i\) for \(S\subseteq N\). If f(s) is a (increasing and concave) cost function, then it yields a cooperative game (N, f, q) by defining characteristic function \(v(S)=f(q_S)\) for \(S\subseteq N\). We now consider the way of taking packages of goods by customers and define a communication graph L on N, in which i and j are linked if they can take packages for each other. So if i and j are connected, then a package can be delivered from i to j by some intermediators. We thus admit any connected subset as a feasible coalition, and obtain a game (N, f, q, L) by defining characteristic function \(v_L(S)=\sum _{R\in S/L}f(q_R)\) for \(S\subseteq N\), where S / L is the family of induced components (maximal connected subset) in S. It is shown that there is an allocation (cost shares) \(x=(x_1,\dots ,x_n)\) from the core for the game (\(x_S\le v_L(S)\) for any \(S\subseteq N\)) such that x satisfies Component Efficiency and Ranking for Unit Prices. If f(s) and q satisfy some further condition, then there is an allocation x from the core such that x satisfies Component Efficiency, and \(x_i \le x_j\) and \(\frac{x_i}{q_i} \ge \frac{x_j}{q_j}\) if \(q_i \le q_j\) for i and j in the same component of N.     

Maximum coverage problem with group budget constraints

We study the maximum coverage problem with group budget constraints (MCG). The input consists of a ground set X, a collection \(\psi \) of subsets of X each of which is associated with a combinatorial structure such that for every set \(S_j\in \psi \), a cost \(c(S_j)\) can be calculated based on the combinatorial structure associated with \(S_j\), a partition \(G_1,G_2,\ldots ,G_l\) of \(\psi \), and budgets \(B_1,B_2,\ldots ,B_l\), and B. A solution to the problem consists of a subset H of \(\psi \) such that \(\sum _{S_j\in H} c(S_j) \le B\) and for each \(i \in {1,2,\ldots ,l}\), \(\sum _{S_j \in H\cap G_i}c(S_j)\le B_i\). The objective is to maximize \(|\bigcup _{S_j\in H}S_j|\). In our work we use a new and improved analysis of the greedy algorithm to prove that it is a \((\frac{\alpha }{3+2\alpha })\)-approximation algorithm, where \(\alpha \) is the approximation ratio of a given oracle which takes as an input a subset \(X^{new}\subseteq X\) and a group \(G_i\) and returns a set \(S_j\in G_i\) which approximates the optimal solution for \(\max _{D\in G_i}\frac{|D\cap X^{new}|}{c(D)}\). This analysis that is shown here to be tight for the greedy algorithm, improves by a factor larger than 2 the analysis of the best known approximation algorithm for MCG.     

On zero-sum $$\mathbb {Z}_{2j}^k$$-magic graphs

Let \(G = (V,E)\) be a finite graph and let \((\mathbb {A},+)\) be an abelian group with identity 0. Then G is \(\mathbb {A}\)-magic if and only if there exists a function \(\phi \) from E into \(\mathbb {A} - \{0\}\) such that for some \(c \in \mathbb {A}, \sum _{e \in E(v)} \phi (e) = c\) for every \(v \in V\), where E(v) is the set of edges incident to v. Additionally, G is zero-sum \(\mathbb {A}\)-magic if and only if \(\phi \) exists such that \(c = 0\). We consider zero-sum \(\mathbb {A}\)-magic labelings of graphs, with particular attention given to \(\mathbb {A} = \mathbb {Z}_{2j}^k\). For \(j \ge 1\), let \(\zeta _{2j}(G)\) be the smallest positive integer c such that G is zero-sum \(\mathbb {Z}_{2j}^c\)-magic if c exists; infinity otherwise. We establish upper bounds on \(\zeta _{2j}(G)\) when \(\zeta _{2j}(G)\) is finite, and show that \(\zeta _{2j}(G)\) is finite for all r-regular \(G, r \ge 2\). Appealing to classical results on the factors of cubic graphs, we prove that \(\zeta _4(G) \le 2\) for a cubic graph G, with equality if and only if G has no 1-factor. We discuss the problem of classifying cubic graphs according to the collection of finite abelian groups for which they are zero-sum group-magic.     

A quadratic time exact algorithm for continuous connected 2-facility location problem in trees

This paper studies the continuous connected 2-facility location problem (CC2FLP) in trees. Let \(T = (V, E, c, d, \ell , \mu )\) be an undirected rooted tree, where each node \(v \in V\) has a weight \(d(v) \ge 0\) denoting the demand amount of v as well as a weight \(\ell (v) \ge 0\) denoting the cost of opening a facility at v, and each edge \(e \in E\) has a weight \(c(e) \ge 0\) denoting the cost on e and is associated with a function \(\mu (e,t) \ge 0\) denoting the cost of opening a facility at a point x(e, t) on e where t is a continuous variable on e. Given a subset \(\mathcal {D} \subseteq V\) of clients, and a subset \(\mathcal {F} \subseteq \mathcal {P}(T)\) of continuum points admitting facilities where \(\mathcal {P}(T)\) is the set of all the points on edges of T, when two facilities are installed at a pair of continuum points \(x_1\) and \(x_2\) in \(\mathcal {F}\), the total cost involved in CC2FLP includes three parts: the cost of opening two facilities at \(x_1\) and \(x_2\), K times the cost of connecting \(x_1\) and \(x_2\), and the cost of all the clients in \(\mathcal {D}\) connecting to some facility. The objective is to open two facilities at a pair of continuum points in \(\mathcal {F}\) to minimize the total cost, for a given input parameter \(K \ge 1\). This paper focuses on the case of \(\mathcal {D} = V\) and \(\mathcal {F} = \mathcal {P}(T)\). We first study the discrete version of CC2FLP, named the discrete connected 2-facility location problem (DC2FLP), where two facilities are restricted to the nodes of T, and devise a quadratic time edge-splitting algorithm for DC2FLP. Furthermore, we prove that CC2FLP is almost equivalent to DC2FLP in trees, and develop a quadratic time exact algorithm based on the edge-splitting algorithm. Finally, we adapt our algorithms to the general case of \(\mathcal {D} \subseteq V\) and \(\mathcal {F} \subseteq \mathcal {P}(T)\).     

The longest commonly positioned increasing subsequences problem

Based on the well-known longest increasing subsequence problem and longest common increasing subsequence (LCIS) problem, we propose the longest commonly positioned increasing subsequences (LCPIS) problem. Let \(A=\langle a_1,a_2,\ldots ,a_n\rangle \) and \(B{=}\left\langle b_1,b_2,\ldots ,b_n\right\rangle \) be two input sequences. Let \({ Asub}=\left\langle a_{i_1},a_{i_2},\ldots ,a_{i_l}\right\rangle \) be a subsequence of A and \({ Bsub}=\left\langle b_{j_1},b_{j_2},\ldots ,b_{j_l}\right\rangle \) be a subsequence of B such that \(a_{i_k}\le a_{i_{k+1}}, b_{j_k}\le b_{j_{k+1}}(1\le k<l)\), and \(a_{i_k}\) and \(b_{j_k}\) (\(1\le k\le l\)) are commonly positioned (have the same index \(i_k=j_k\)) in A and B respectively but these two elements do not need to be equal. The LCPIS problem aims at finding a pair of subsequences Asub and \({ Bsub}\) as long as possible. When all the elements of the two input sequences are positive integers, this paper presents an algorithm with \(O(n\log n \log \log M)\) time to compute the LCPIS, where \(M={ min}\{{ max}_{1\le i\le n}a_i,{ max}_{1\le j\le n}b_j\}\). And we also show a dual relationship between the LCPIS problem and the LCIS problem.