Loading [MathJax]/jax/output/SVG/jax.js
Research article Special Issues

Uniqueness for meromorphic solutions of Schwarzian differential equation

  • Received: 09 April 2021 Accepted: 17 August 2021 Published: 02 September 2021
  • MSC : 30D35

  • Let f be a meromorphic function, R be a nonconstant rational function and k be a positive integer. In this paper, we consider the Schwarzian differential equation of the form

    [ff32(ff)2]k=R(z).

    We investigate the uniqueness of meromorphic solutions of the above Schwarzian differential equation if the meromorphic solution f shares three values with any other meromorphic function.

    Citation: Dan-Gui Yao, Zhi-Bo Huang, Ran-Ran Zhang. Uniqueness for meromorphic solutions of Schwarzian differential equation[J]. AIMS Mathematics, 2021, 6(11): 12619-12631. doi: 10.3934/math.2021727

    Related Papers:

    [1] Shiyong Zhang, Qiongfen Zhang . Normalized solution for a kind of coupled Kirchhoff systems. Electronic Research Archive, 2025, 33(2): 600-612. doi: 10.3934/era.2025028
    [2] Jiayi Fei, Qiongfen Zhang . On solutions for a class of Klein–Gordon equations coupled with Born–Infeld theory with Berestycki–Lions conditions on R3. Electronic Research Archive, 2024, 32(4): 2363-2379. doi: 10.3934/era.2024108
    [3] Shuai Yuan, Sitong Chen, Xianhua Tang . Normalized solutions for Choquard equations with general nonlinearities. Electronic Research Archive, 2020, 28(1): 291-309. doi: 10.3934/era.2020017
    [4] Tao Zhang, Tingzhi Cheng . A priori estimates of solutions to nonlinear fractional Laplacian equation. Electronic Research Archive, 2023, 31(2): 1119-1133. doi: 10.3934/era.2023056
    [5] Haijun Luo, Zhitao Zhang . Existence and stability of normalized solutions to the mixed dispersion nonlinear Schrödinger equations. Electronic Research Archive, 2022, 30(8): 2871-2898. doi: 10.3934/era.2022146
    [6] Xiaoyong Qian, Jun Wang, Maochun Zhu . Existence of solutions for a coupled Schrödinger equations with critical exponent. Electronic Research Archive, 2022, 30(7): 2730-2747. doi: 10.3934/era.2022140
    [7] Chungen Liu, Huabo Zhang . Ground state and nodal solutions for fractional Kirchhoff equation with pure critical growth nonlinearity. Electronic Research Archive, 2021, 29(5): 3281-3295. doi: 10.3934/era.2021038
    [8] Christos Sourdis . A Liouville theorem for ancient solutions to a semilinear heat equation and its elliptic counterpart. Electronic Research Archive, 2021, 29(5): 2829-2839. doi: 10.3934/era.2021016
    [9] Yaning Li, Yuting Yang . The critical exponents for a semilinear fractional pseudo-parabolic equation with nonlinear memory in a bounded domain. Electronic Research Archive, 2023, 31(5): 2555-2567. doi: 10.3934/era.2023129
    [10] Milena Dimova, Natalia Kolkovska, Nikolai Kutev . Global behavior of the solutions to nonlinear Klein-Gordon equation with critical initial energy. Electronic Research Archive, 2020, 28(2): 671-689. doi: 10.3934/era.2020035
  • Let f be a meromorphic function, R be a nonconstant rational function and k be a positive integer. In this paper, we consider the Schwarzian differential equation of the form

    [ff32(ff)2]k=R(z).

    We investigate the uniqueness of meromorphic solutions of the above Schwarzian differential equation if the meromorphic solution f shares three values with any other meromorphic function.



    Several variants of combinatorial optimization problems are defined on the path structure in graphs. One of the most important problems is the maximum capacity path problem. It is to find a path joining two prescribed nodes whose capacity, that is the minimum capacity of its arcs, is maximized. This problem is also known as the bottleneck path problem, the max-min path problem, and the widest path problem. Due to the fact that the problem can be seen as a network flow optimization problem, it admits a wide range of applications. For example, in telecommunication networks, the Multiprotocol Label Switching (MpLS) is a protocol to send a packet along a path whose minimum bandwidth is maximized [11]. As another application, single service units (e.g., fire fighter, police) estimate the quality of a route by the maximum distance to an available service location [5].

    As other instances of combinatorial optimization problems defined on path structure, shortest and longest path problems have completely different behaviours: the shortest path problem is polynomially solvable, whereas the longest path problem is NP-hard in general [3]. However, the maximum capacity path problem and its minimum version, namely the min-max path problem, have the same behaviour. Indeed, one can use any algorithm solving one to obtain an optimal path of the other. A recursive algorithm is the best-known algorithm that is capable of solving maximum capacity path problems in linear time [15].

    This paper concentrates on an inverse version of maximum capacity path problems, called the maximum capacity path expansion problem. In general, three types of inverse problems are definable for any optimization problem:

    ● Given an initial feasible solution, the goal is to change some parameters of the problem as little as possible so that the solution becomes optimal.

    ● The problem is to change some parameters as little as possible such that the objective value of the optimization problem is bounded by a prescribed value.

    ● The goal is to modify some parameters under a budget constraint in a way that the optimal value of the optimization problem is improved as much as possible.

    It is customary that the first category is called the inverse optimization [9,10,20]. To distinguish from the first, the problems belonging to the second category are referred to as the reverse optimization problems [18,19], and optimization improvement problems [24,25]. Third category has not any formal name in the literature. However, for the special case that the objective function is bottleneck-type (namely, min-max or max-min), the third category's problems are called the bottleneck capacity expansion problems (BCEPs) [13,23,26]. It is obvious that the problems of second and third categories have a close relationship together because if one interchanges the objective function and the budget constraint of a problem in the third category, then its corresponding problem in the second category is obtained.

    Suppose that E={e1,e2,,em} is a ground set and F2E. Let each eiE be associated to a capacity ci. A (max-min) bottleneck-type combinatorial optimization problem is to find a fF so that the minimum capacity of its elements is maximized, i.e.,

    maxfFmineifci. (1.1)

    This problem is an extension of several combinatorial optimization problems, such as maximum capacity path problem [14], max-min spanning tree problem [21].

    For every type of problem (1.1), one can define a capacity expansion problem. It is to increase capacities under some budget and bound constraints so that the capacity of the optimal solution of problem (1.1) is increased as much as possible. This problem is the same BCEP which can be formulated as

    maxxiXmaxfFmineifci+xi, (1.2)

    in which X is a feasible region to restrict capacity increments.

    Yang and Zhang [22] were the first in considering BCEPs defined on networks. They studied the problem of increasing arc capacities under a budget constraint so that the capacities of maximum capacity paths between every pair of nodes are maximized. They proposed a strongly polynomial-time algorithm which requires to solve a minimum spanning tree at every iteration. Subsequently, Chao and Jinglin [8] investigated the capacity expansion problem in spanning trees. They showed that the problem is reducible to a parametric spanning tree problem. Then, they presented a strongly polynomial-time algorithm to solve the problem. Li and Zhu [13] used the dynamic programming technique to present a pseudopolynomial-time algorithm for expanding the capacity of maximum capacity path from a source to a sink. Then, they designed polynomial-time algorithms for two special cases of the problem. Bukard et al. [6] studied the weight reduction problems with the min-max objective function, instead of max-min. They proved that the problem is NP-hard in general. Then, they reduced the problem to a parametric optimization problem which can be used for solving the problem in the special case of spanning trees. Chao and Jianzhong [7] considered three types of BCEPs (path, spanning-tree, and maximum flow) in two arc-expanding and node-expanding cases. They presented some results on their complexity.

    BCEPs are also studied in the general case. A modified binary search algorithm [23] and a discrete-type Newton algorithm [26] are presented to solve BCEPs in the general case.

    As a special case of BCEPs, this paper focuses on the maximum capacity path expansion problem (MCPEP) in two distinct cases: (I) fixed modification costs; (II) linear modification costs. To the best of our knowledge, the fixed-cost case is not investigated in the literature. In this case, a simple algorithm based on binary search is presented to solve the problem in strongly polynomial time. In the linear-cost case, a two-phase algorithm is developed to solve the problem in polynomial time. The first phase applies the same fixed-cost algorithm to find an interval containing the optimal value. The second phase converts the resulted problem into a maximum ratio path problem. Then, it uses a proposed hybrid Secant-Newton algorithm to solve exactly the problem. To validate our proposed algorithm, we theoretically and computationally compare it with the algorithms presented in [23] and [26].

    Let us now state an application of MCPEP in transforation systems. Depending on the type of vehicle crossing a road, a capacity can be assigned to each road. For example, if only light vehicles are allowed to pass, the capacity can be equal to a small number, and if any type of light and heavy vehicles is allowed to pass, the capacity can be equal a large number. The capacity of a road depends on various factors such as road width, and road infrastructure. It is clear that the capacity of a route is equal to the minimum capacity of its roads. Now suppose we want to increase road capacities under a budget constraint so that heavy vehicles can pass between two specific points. This is a typical application of MCPEPs.

    The rest of this paper is organized as follows. Section 2 states formally the problem and gives some initial results. Section 3 concentrates on the problem with fixed costs. Section 4 focuses on the problem with linear costs. It presents a strongly polynomial-time algorithm and compares it with the others. Section 5 presents our concluding remarks.

    This section recalls the definition of maximum capacity path problems and introduces its expansion version. Then, it presents some initial results used throughout the paper.

    Suppose that a connected and directed network G(V,A,c) is given in which V={1,2,,n} is the node set; A is the arc set containing m arcs. Each arc (i,j) is associated to a nonnegative capacity cij. The network contains two specific nodes s and t which are called the origin and the destination, respectively. A sequence v0v1vk of nodes is said to be a walk if (vi1,vi)A for i=1,2,,k. A path is a walk without any repetition of nodes. A cycle is a path v0v1vk together with the arc (vk,v0). It is obvious that one can simply obtain a path from a given walk P by removing its all cycles. This paper concentrates on paths from the origin s to the destination t, called st-paths. Any st-path P has a capacity cP which is the minimum capacity of its arcs, i.e., cP=min(i,j)Pcij.

    A classical combinatorial optimization problem, called the maximum capacity path problem (MCPP), is to find an st-path whose capacity is the maximum among all st-paths. Similar to the formulation of shortest path problems [3], one can simply formulate MCCP in the form of a zero-one linear programming problem as follows:

    maxz (2.1a)
    s.tzcij+C(1xij) (2.1b)
    (i,j)A+ixij(j,i)Aixji={1i=s,0is,t,1i=t,ıV, (2.1c)
    (i,j)A+ixij1iV, (2.1d)
    xij{0,1}(i,j)A. (2.1e)

    in which C=max(i,j)A{cij}. Constraint (2.1b) guarantees that z equals the maximum capacity of the path P determined by constraints (2.1c). xij is a zero-one variable which takes one if and only if (i,j) belongs to the desired path P. The purpose of A+i (Ai) is the set of arcs enumerating from (terminating at) i. Moreover, constraint (2.1d) is added to prevent node repetitions in the obtained path. On the other word, the solution is a path, and not only a walk. If the objective value of problem (2.1) is equal to z, then we simply say that the maximum capacity of G(V,A,c) is z.

    Now let us define the expansion version of problem (2.1). Suppose that we are capable of increasing arc capacities under some budget and bound constraints, and we would like improve the optimal value of problem (2.1) as much as possible. This problem can be formulated as follows:

    maxz (2.2a)
    s.tzcij+yij+Cu(1xij) (2.2b)
    (i,j)A+ixij(j,i)Aixji={1i=s,0is,t,1i=t,ıV, (2.2c)
    (i,j)A+ixij1iV, (2.2d)
    (i,j)Abij(yij)B, (2.2e)
    0yijcuijcij(i,j)A, (2.2f)
    xij{0,1}(i,j)A, (2.2g)

    in which Cu=max(i,j)A{cuij}, and yij is a continuous variable to determine the increment amount of capacity in (i,j); cuij is an upper bound for increasing the capacity of (i,j); bij(.) is a nonnegative, real-valued and nondecreasing function to measure the cost of increasing the capacity of (i,j). Moreover it satisfies the property that bij(0)=0. The other notations are defined the same as problem (2.1).

    Without the loss of generality, we may impose the following assumption to problem.

    Assumption 1. Each arc of the network belongs to at least an st-path.

    Assumption 1 is not restrictive because if not, one can perform two arc traversals, one time from s and another time from t in the opposite direction of arcs. The double-traversed arcs satisfy the assumption. So removing the other arcs satisfies Assumption 1. Obviously, this procedure can be performed in O(m) time.

    This paper focuses on problem (2.2) for two distinct cost functions:

    Fixed costs: In this case, it is assumed that bij(yij) is equal to zero for yij=0 and a positive fixed value ˉwij for yij>0. In the inverse optimization context [12,17], bij(yij)=ˉwijH(0,yij), where H(0,yij) is the Hamming distance between 0 and yij defined as

    H(0,yij)={0yij=0,1yij0.

    Linear costs: This case is to assume that bij(yij)=wijyij in which wij>0 is the cost of per unit increment of the capacity. So bij(.) is a linear function with the slope wij and the y-intercept 0. In the literature, the sum of these linear cost functions are called the weighted Manhattan distance [4,21].

    A simple observation of problem (2.2) is that yij=0, (i,j)A, is a feasible solution whose objective value zmin is equal to the maximum capacity of G(V,A,c). So it provides a lower bound for the optimal value z of problem (2.2). On the other hand, yij=cuijcij, (i,j)A, tights bound constraints (2.2f), but it may not satisfy budget constraint (2.2e). So its objective value, denoted by zmax, provides an upper bound for z. Notice that zmax is obtained directly from bound constraints even without noting the budget constraint. In the case of linear costs, a new upper bound can be obtained as zmin+BwL in which wL=min(i,j)Awij because for (i,j)A with xij=1, we have

    wijzwijcij+wijyijwijcij+B,(i,j)A,

    which the last inequality hold due to the budget constraint. This inequality implies the upper bound zmin+BwL if we assume that (i,j) is the arc which determines the initial maximum capacity of the network. In the case of fixed costs, a similar proof can be done to achieve this upper bound. Let us state formally these observations.

    Lemma 2.1. The optimal value of problem (2.2) belongs to

    [ˉzmin,ˉzmax]=[zmin,min{zmax,zmin+BwL}]

    where zmin and zmax are respectively the maximum capacities of G(V,A,cij) and G(V,A,cuij), and

    wL={min(i,j)Awijfor linear costs, min(i,j)Aˉwijfor fixed costs.

    Proof. The proof is straightforward based on the preceding paragraph.

    For an st-path P as well as a fixed value z[ˉzmin,ˉzmax], consider a capacity vector c(z,P) defined as

    c(z,P)ij={z(i,j)Pz(cij,cuij],cijotherwise,(i,j)A. (2.3)

    The following lemma shows that we can restrict ourselves to such capacity vectors to find an optimal solution of problem (2.2).

    Lemma 2.2. If ˉc is a feasible capacity vector to problem (2.2), then c(ˉz,ˉP) is also feasible, where ˉP is a maximum capacity path with respect to ˉc, and ˉz is its capacity. Moreover, the objective values of both the vectors are the same.

    Proof. It is easy to see that c(ˉz,ˉP)ijˉcij for every (i,j)A. This simple observation together with the feasibility of ˉc imply that c(ˉz,ˉP) satisfies the bound and budget constraints. On the other hand, by definition, the capacity of ˉP with respect to c(ˉz,ˉP) is exactly equal to ˉz. So the objective value of c(ˉz,ˉP) is the same as that of ˉc.

    Notice that the capacity vector c(z,P) is defined with respect to an st-path P as well as a value z[ˉzmin,ˉzmax]. As seen in Lemma 2.2, z depends on P. On the other word, if P is determined, then we can simply compute z because it is the minimum capacity of arcs belonging to P. Let us now ask this question: Is there a convenient st-path P for a given value z? To reply this question, consider a cost vector w(z) defined as follows:

    w(z)ij={+z>cuij,bij(zcij)cij<zcuij,0zcij,(i,j)A. (2.4)

    The following lemma clarifies the relationship between w(z) and our question.

    Lemma 2.3. For a fixed value z, let ˉP be a shortest st-path with respect to w(z). Then,

    1). c(z,ˉP) is a feasible solution of problem (2.2) if the length of ˉP is less than or equal to B.

    2). There is not any st-path P so that c(z,P) is a feasible solution of problem (2.2) if the length of ˉP is greater than B.

    Proof. The proof of the first part is trivial. To prove the second part, by contradiction, suppose that c(z,˜P) is feasible for some st-path ˜P. So c(z,˜P) satisfies the budget constraint. This together with the assumption that the length of ˉP is greater than B imply that the length of ˜P is less than that of ˉP with respect to w(z). This is a contradiction because ˉP is a shortest st-path.

    This section studies problem (2.2) with fixed costs. It presents an algorithm to solve the problem in strongly polynomial time.

    According to Lemma 2.3, problem (2.2) reduces to finding the greatest value z[ˉzmin,ˉzmax] so that the length of the shortest st-path with respect to w(z) does not exceed B. This result motivates us to apply a binary search procedure for finding such value z. The following lemma aids us to limit the search interval only to a finite set.

    Lemma 3.1. The optimal value of problem (2.2) with fixed costs belongs to the finite set S=(i,j)A{cij,cuij}[ˉzmin,ˉzmax].

    Proof. By contradiction, assume that z is the optimal value not belonging to S. So there is an st-path P so that c(z,P) is the optimal capacity vector. Sort the distinct elements of S in a nondecreasing order and let z1<z2<<zk be the sorted list. So there is an index l{2,,k} so that zl1<z<zl. Now, consider the capacity vector c(zl,P). It is easy to prove that this vector satisfies the bound and budget constraints, and moreover, its optimal value is equal to zl. This contradicts the fact that z is the optimal value.

    Algorithm 1 presents a binary search in complete details for solving problem (2.2).

    Algorithm 1 Solving problem (2.2) with fixed costs.
      Input: An instance of problem (2.2) with fixed costs defined on a network G(V,A,c,w) with two specified nodes s and t in which c is initial capacity vector and w is fixed cost vector.
      Output: An optimal st-path P, and the optimal value z.
      Set zmax to the length of the maximum capacity path with respect to capacities cuij.
      Find a shortest path P with respect to w(zmax).
      if The length of P less than or equal to B then
        Stop because the problem has the optimal path P=P, and the maximum capacity z=zmax.
      end if
      Set ˉzmin to the length of the maximum capacity path with respect to capacities cij.
      Set ˉzmax=min{zmax,ˉzmin+BwL} where wL=min(i,j)Awij.
      Sort the distinct elements of S=(i,j)A{cij,cuij}[ˉzmin,ˉzmax]. Let z1<z2<<zk be the sorted list.
      Set l=1, u=k.
      while l<u do
        Set mid=[l+u2].
        Find a shortest path P with respect to wzmid.
        if The length of P less than or equal to B then
          Set l=mid, z=zmid, and P=P.
        else
          Set u=mid.
        end if
      end while

     | Show Table
    DownLoad: CSV

    Theorem 3.2. Algorithm 1 solves problem (2.2) in strongly polynomial time.

    Proof. The correctness of Algorithm 1 follows from the results presented in Lemma 3.1 and the preceding section. So let us argue only about its complexity. The bottleneck operation of Algorithm 1 is to solve a shortest path problem in the While loop. Since the While loop runs O(log(2m))=O(log(n)) times, and the Fibonacci heap implementation of Dijkstra's algorithm requires O(m+nlog(n)) computations, it follows that Algorithm 1 solves problem (2.2) in O(mlog(n)+nlog2(n)) time.

    This section concentrates on problem (2.2) whenever the cost of (i,j) is a linear function as bij(yij)=wijyij. Although Lemma 2.3 remains valid in this case, the issue is not as simple as the fixed-cost case because the search space is a continuous interval, instead of a finite set.

    To develop an algorithm for solving problem (2.2) with linear costs, consider the function b(z) which is the length of the shortest st-path with respect to the weight vector w(z), i.e.,

    b(z)=minPP(z)(i,j)Pmax{0,wij(zcij)}. (4.1)

    Here, P(z) denotes the set of all st-paths which have not any intersection with the set {(i,j):w(z)ij=+}={(i,j):z>cuij}. In the special case that there is not any st-path for some value z, we set b(z)=+. Since b(z) is a parametric shortest path function in terms of z, it follows that it is non-decreasing and piecewise-linear, but unfortunately, it does not enjoy any convexity and concavity property in general. However, we show that b(z) is concave in a small subinterval of [ˉzmin,ˉzmax] containing the optimal value.

    Before paying attention to these details, let us state a general description of our proposed algorithm which contains two phases. In the first phase, the binary search is applied to find a subinterval of [ˉzmin,ˉzmax] in which b(z) is concave. In the second phase, the exact optimal value is found by a new hybrid Secant-Newton algorithm.

    Let us now return to analysing the behaviour of b(z). It is obvious that b(z) is increasing. Whenever z increases continuously, the breakpoints of b(z) are created in one of three following situations.

    ● The shortest path is changed. So the slope of the corresponding line in b(z) is either fixed or decreased.

    ● The shortest path is not changed. However, the weight of its one arc is increased from zero to a positive value. In this case, the slope of the corresponding line in b(z) is increased.

    ● For an arc (i,j) of the shortest path P, we have z>cuij. In this situation, the length of P grows unexpectedly to + because w(z)ij=+. So the second shortest path is replaced to P. Consequently, the slope of the corresponding line in b(z) is either unchanged or increased.

    If the search interval [ˉzmin,ˉzmax] is reduced so that the second and third cases never occur, then b(z) is concave based on the first case. For this purpose, we reconsider the sorted list z1<z2<<zk of the set S. Then, we find an index l{1,2,,k1} so that the optimal value belongs to [zl,zl+1). Obviously, the second and third cases does not occur in this interval. This procedure can be done perfectly by Algorithm 1 under the assumption that bij(zl)=wij(zlcij), instead of bij(z)=ˉwij. Hence, the first phase applies Algorithm 1 as a subroutine to find an interval [zl,zl+1) containing the optimal value. The following result states the concept used in the second phase.

    Lemma 4.1. If the optimal value z is less than ˉzmax, then b(z)=B.

    Proof. By definition, it is obvious that the function b(z) is strictly increasing in [ˉzmin,ˉzmax), and it is constant elsewhere. Since z<ˉzmax, it follows that there is an index l so that z[zl,zl+1). Based on Lemma 2.2, we know that there is an st-path P so that c(z,P) is the optimal capacity vector.

    Now assume that b(z) is less than B by contradiction. So we can find a value z(z,zl+1) so that P is the shortest path with respect to w(z) and c(z,P) satisfies the budget constraint. Since c(z,P) satisfies the bound constraints and both the values z,z belong to [zl,zl+1), we imply that c(z,P) also satisfies the bound constraints. Hence, c(z,P) is a feasible capacity vector with the objective value greater than z which contradicts the optimality of c(z,P).

    Based on Lemma 4.1, problem (2.2) is reduced to finding a root of the equation b(z)=B in the interval [zl,zl+1). Since b(z) is strictly increasing in this interval, it follows that the root is unique. The equation b(z)=B can be rewritten as

    minPP(z)(i,j)P:cijzwij(zcij)=B. (4.2)

    in which P(z) is defined the same as 4.1. So it is dependent on z. Using the fact that the search interval is restricted to [zl,zl+1), we can write the equation in the following fashion:

    minPP(zl)(i,j)P:cijzlwij(zcij)=B. (4.3)

    Now suppose that (z,P) is an optimal solution of problem (4.3). Trivially, we have

    (i,j)P:cij>zlwij(zcij)=B, (4.4)
    (i,j)P:cij>zlwij(zcij)B,PP(zl). (4.5)

    These relations imply that

    B+(i,j)P:cijzlwijcij(i,j)P:cijzlwij=zB+(i,j)P:cijzlwijcij(i,j)P:cijzlwijPP(zl). (4.6)

    So the following result is immediate.

    Theorem 4.2. If the optimal value of Problem (2.2) belongs to [zl,zl+1), then the problem is reduced to a minimum ratio path problem as follows:

    minPP(zl)z=B+(i,j)P:cijzlwijcij(i,j)P:cijzlwij. (4.7)

    Problem (4.7) is a minimum cost-reliability ratio path problem which is NP-hard in general because it is possible that there are some negative cycles in the network with respect to the cost vector w(z) [1,2]. Fortunately, since we have assumed that the costs w(z)ij are nonnegative, the problem can be solved efficiently by Newton discrete-type method [16]. This is the same concept used by Zhang and Liu [26] to solve BCEPs. Let us recall their proposed method. It generates an increasing sequence {z(k)}k=0,1, starting z(0)=zl. Suppose that the algorithm has computed the value z(k). To calculate the next element of the sequence, the algorithm solves a shortest path problem with respect to the nonnegative length vector

    v=w(z(k)). (4.8)

    Assume that path P is found. Now, we may encounter two distinct situations:

    ● The length of P is less than B. In this case, we have

    B>(i,j)Pvij=(i,j)P:cijz(k)wij(z(k)cij)z(k)<B+(i,j)P:cijzlwijcij(i,j)P:cijzlwij,

    So we can set z(k+1) equal to the right-hand term of this inequality.

    ● The length of P is exactly equal to B. In this case, P is an optimal solution of problem (4.7) because P satisfies (4.4) and all st-paths satisfy (4.5) for z=z(k). So inequalities (4.6) hold for z=z(k).

    It is remarkable that the case that the length of P is greater than B never occurs [26].

    This algorithm generates an increasing sequence converging the optimal value. However, due to the special structure of b(z), it always approaches to the optimal value only from one side, and it does not use points of the other side. For example, the sequence generated by algorithm present in [26] is as

    zl=z(0)<z(1)<z(2)<<z<zl+1.

    So the algorithm does not use any point in [z,zl+1] to find z. Specially, if z is very close to zl+1, then the algorithm has to approximately traverse all length of [zl,zl+1) to look for the optimal value. Here, we present a hybrid Secant-Newton algorithm to approach both the side of the optimal value. This algorithm generates two sequence {z(k)} and {y(k)} starting z(0)=zl and y(0)=zl+1. Assume that we have computed the kth elements of both the sequences. Their next elements are calculated as follows:

    y(k+1)=y(k)b(z(k))z(k)b(y(k))y(k)z(k)B, (4.9)
    z(k+1)=max{ˆz(k),ˆy(k)}, (4.10)

    in which

    ˆy(k)=y(k)b(y(k+1))y(k+1)b(y(k))y(k)y(k+1)B, (4.11)
    ˆz(k)=B+(i,j)P:cijzlwijcij(i,j)P:cijzlwij. (4.12)

    y(k+1) is obtained from solving the equation L(z)=B where L(z) is the line joining two points (y(k),b(y(k))) and (z(k),b(z(k))). This is motivated to use the well-known Secant method in computing the root of an equation. ˆz(k) is the same approximation obtained from the Newton method and ˆy(k) is the approximation obtained from the Secant method using two consecutive values y(k) and y(k+1). Finally, z(k+1) is the maximum value of two calculated approximation. Since z(k+1)ˆz(k), it follows that the number of iterations at the hybrid method is at most equal to that of the Newton method. So {z(k)} converges the optimal value at the end. Figure 1 depicts a visual description of the hybrid Secant-Newton method. It is easy to see that the sequence {z(k)} ({y(k)}) is increasing (decreasing) and approaches to the optimal value from the left (right) side. The running time of an iteration of the hybrid algorithm is at most three times of the Newton method's because it calls the function b(z) three times. Hence its worst-case complexity is the same as the Newton method. This proves the following result.

    Figure 1.  A visual description of the hybrid Secant-Newton method.

    Theorem 4.3. Algorithm 2 solves problem (2.2) in strongly polynomial time.

    Algorithm 2 A hybrid Secant-Newton method to solve problem (2.2) with linear costs
     Input: A network G(V,A,c,w) with two specified nodes s and t
     Output: An optimal st-path P, and the optimal value z.
     Phase I:
     Apply Algorithm 1 as a subroutine for arc costs bij(zl)=wij(zlcij) to either detect the optimal value is zmax or find an interval [zl,zl+1) containing the optimal value. In the former, stop because the optimal value is found. In the latter, go to Phase II.
     Phase II:
     Set z=zl.
     Set y=zl+1.
     while True do
        Obtain the length vector v defined in (4.8) for z(k)=z.
        Find shortest path P with respect to the length vector v.
        if the length of P equals B then
           Stop because the optimal solution is found (see Lemma 4.1).
        else
           Set y=y(k)b(z(k))z(k)b(y(k))y(k)z(k)B.
           Set z=max{yb(y)yb(y)yyB,B+(i,j)P:cijzlwijcij(i,j)P:cijzlwij}.
           Set y=y.
        end if
     end while

     | Show Table
    DownLoad: CSV

    Proof. The proof is immediate from the above discussion and the fact that the Newton method solves the problem in strongly polynomial time [26].

    We now compare Algorithm 2 with the available algorithms in the literature. We recall that a modified binary search algorithm and a Newton discrete-type algorithm are presented respectively in [23] and [26] to solve BCEPs. Since MCPEP is a special case of BCEPs, we can apply them to solve MCPEP. Based on our preceding discussion, Algorithm 2 has the same worst-case complexity of the algorithm proposed in [26] which runs in strongly polynomial time. Moreover, the algorithm presented in [23] is only a (weak) polynomial time algorithm. This implies that Algorithm 2 as well as one proposed in [26] are theoretically better than one provided in [23].

    Let us now compare them in practice. We recall that b(z) is a linear-piecewise function. In instances of MCPEP for which b(z) has a many number of breakpoints in the search interval [zl,zl+1] of the second phase, Algorithm 2 has a better performance than the others. This occurs specially whenever the upper bounds are infinity and the amount of budget is very large because in this case,

    ● The initial search interval [zmin,zmax]=[z0,zk], specially subinterval [zk1,zk], is very wide;

    ● The search interval in the second phase is usually the same interval [zk1,zk] containing many numbers of b(z)'s breakpoints.

    Let us state an example in this case. Consider an instance of MCPEP shown in Figure 2. Here, it is assumed that B=39, s=0 and t=37. Moreover, all upper bounds are + and wij=0.01 for every arc (i,j)A. In this example, we have [zmin,min{zmin+BwL,zmax}]=[3200,7100] at which the function b(z) contains 8 breakpoints (see Figure 3). This interval is the same interval [zl,zl+1] containing the optimal value. For this example, the algorithms were implemented on a laptop with an Intel Core i52520M CPU (2.50GHz) and 4 GB of RAM. To code the algorithms, Python 2.7.5 together with the library NetworkX 1.8.1 were used. Table 1 compares the performance of the algorithms. It is obvious that Algorithm 2 has solved the problem in a less number of iterations.

    Figure 2.  An instance of MCPEP with s=0 and t=37.
    Figure 3.  The graph of b(z) at [3200,7100].
    Table 1.  Comparing the algorithms in an instance of MCPEP.
    Number of iterations Running time (sec.) Values z in all iterations
    Alg. in [23] 3 0.037 3900, 3875, 3950
    Alg. in [26] 4 0.061 3633.33, 3875, 3930, 3950
    Alg. 2 1 0.013 3950

     | Show Table
    DownLoad: CSV

    This paper studied maximum capacity path expansion problems with two types of modification costs: fixed cost, and linear cost. In the former, it proposed a strongly polynomial-time algorithm based on binary search to solve the problem. In the latter, it developed a two-phases algorithm. The first phase uses the first algorithm to find a small interval containing the optimal value at which the cost function is concave. Then, a hybrid Secant-Newton algorithm is proposed to obtain exactly the optimal value. The hybrid algorithm has a admissible performance rather than the available algorithms in the literature.

    Since the hybrid algorithm can be applied to solve general fractional combinatorial optimization problems, it will be meaningful that one compares it with the other customary approaches, such as binary search, discrete-type Newton method, and Meggido's parametric search [16].

    Although there is a variety of studies on capacity expansion problems, there are some aspects that are not considered until now (for example, max-min matching expansion problems, and max-min cut expansion problems). It will be worthwhile to focus on the other expansion problems in the future works.

    We would like to thank the editor and anonymous reviewers for their constructive comments, which helped us to improve the paper.

    We have no conflict of interest to declare.



    [1] G. G. Gundersen, Meromorphic functions that share four values, T. Am. Math. Soc., 277 (1983), 545–567. doi: 10.1090/S0002-9947-1983-0694375-0
    [2] G. G. Gundersen, Correction to "Meromorphic functions that share four values", T. Am. Math. Soc., 304 (1987), 847–850.
    [3] W. K. Hayman, Meromorphic functions, Oxford: Clarendon Press, 1964.
    [4] K. Ishizaki, Admissible solutions of the Schwarzian differential equation, J. Aust. Math. Soc. A., 50 (1991), 258–278. doi: 10.1017/S1446788700032742
    [5] I. Laine, Nevanlinna theory and complex differential equations, Berlin: Walter de Gruyter, 1993.
    [6] L. Liao, Z. Ye, On the growth of meromorphic solutions of the Schwarzian differential equations, J. Math. Anal. Appl., 309 (2005), 91–102. doi: 10.1016/j.jmaa.2004.12.011
    [7] E. Mues, Meromorphic functions sharing four values, Complex Var. Elliptic, 12 (1989), 167–179.
    [8] R. Nevanlinna, Einige Eindentigkeitssätze in der theorie der meromorphen funktionen, Acta Math., 48 (1926), 367–391. doi: 10.1007/BF02565342
    [9] C. C. Yang, H. X. Yi, Uniquenss theory of meromorphic functions, Springer Science & Business Media, 2003.
    [10] L. Yang, Value distribution theory and its new research (in Chinese), Beijing: Science Press, 1982.
  • This article has been cited by:

    1. Adrian M. Deaconu, Javad Tayyebi, Increasing the Maximum Capacity Path in a Network and Its Application for Improving the Connection Between Two Routers, 2024, 29, 1007-0214, 753, 10.26599/TST.2023.9010055
  • Reader Comments
  • © 2021 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

Metrics

Article views(2270) PDF downloads(92) Cited by(1)

Other Articles By Authors

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog