Asia-Pacific Journal of Operational Research

This paper documents the first attempt to apply the differential game theory for investigating some properties of a low-carbon supply chain coordination by employing the cost-sharing mechanism. The manufacturer is the brand owner and the corresponding low-carbon goodwill is increased with respect to the reference emission reduction effect and consumption promotion. Three dynamic games are well-studied by considering the multiple effects of price and non-price factors on the market. It can be observed that the manufacturer always prefers to employ the coordination mechanism. When the manufacturer opts for a cost-sharing program, the manufacturer and retailer under Model-D are always economically better off, and therefore a cost-sharing program is always profit-Pareto-improving.

We investigate the problem of maximizing a $\gamma$-submodular function subject to one or multiple matroid constraints and one knapsack constraint. By the greedy local search technique, we present approximation algorithms with constant approximation ratios. When $\gamma =1$, our model reduces to the regular submodular maximization problem investigated in the literature under the same type of constraints. Our results therefore contribute towards the line of research on constrained non-submodular function maximization.

This paper investigates a classic online scheduling problem with learning effect on a single machine. Specifically, a number of independent jobs that arrive online over time will be processed on a single machine and learning effect implies that the real processing time of job $J_j$ is a non-increasing function of its position $h$, i.e., $p_{jh}=p_j{\alpha }^{h-1}$, where $p_j$ is the basic processing time of job $J_j$ and $0<\alpha <1$ is the learning index. Our goal is to minimize the total completion time of all jobs. For the problem, we develop a deterministic polynomial time online algorithm called Delayed Shortest Basic Processing Time (DSBPT) and state that it is an online algorithm with a competitive ratio of 2, which matches the lower bound of the online scheduling problem we focus on.

In this paper, a single-machine semi-online scheduling problem with rejection is addressed. In this model, “semi-online” implies that $\frac{p_{max}}{p_{min}}\le \gamma$, where $p_{max}$ and $p_{min}$ are the maximum processing time and the minimum one among all jobs, respectively, $\gamma \ge 1$. In this setting, each job arrives online over time, and rejection is allowable. Our goal is minimizing the total penalty cost of rejected jobs plus the total completion time of processed jobs. The seminal result of this study is that we offer an algorithm with competitive ratio $1+\frac{\sqrt{1+\gamma (\gamma -1)}-1}{\gamma }$, which matches the result of the problem without rejection.

Emerging applications such as optimal budget allocation and sensor placement impose problems of maximizing variants of submodular functions with constraints under a streaming setting. In this paper, we first devise a streaming algorithm based on Sieve-Streaming for maximizing a monotone diminishing return submodular (DR-submodular) function with a cardinality constraint on the integer lattice and show it is a one-pass algorithm with approximation ratio $\frac{1}{2}-𝜖$. The key idea to ensure one pass for the algorithm is to combine binary search for determining the level of an element with the exponential-growth method for estimating the OPT. Inspired by Sieve-Streaming++, we then improve the memory of the algorithm to $O(\frac{k}{𝜖})$ and the query complexity to $O(\frac{k{log}^{2}k}{𝜖})$.

Independent set games are cooperative games defined on graphs, where players are edges and the value of a coalition is the maximum size of independent sets in the subgraph defined by the coalition. In this paper, we study population monotonic allocation schemes for independent set games. For independent set games introduced by Deng et al. [X. Deng, T. Ibaraki and H. Nagamochi (1999). Algorithmic aspects of the core of combinatorial optimization games. Mathematics of Operations Research, 24(3), 751–766], we provide a combinatorial characterization for population monotonic allocation schemes in convex instances. For independent set games introduced by Xiao et al. [H. Xiao, Y. Wang and Q. Fang (2021). On the convexity of independent set games. Discrete Applied Mathematics, 291, 271–276], we prove the equivalence of convexity, population monotonicity and balancedness.

We study one scheduling game with activation cost, where each game involves $n$ jobs being processed on $m$ parallel-batching identical machines. Each job, as an agent, selects a machine (more precisely, a batch on a machine) for processing to minimize his disutility, which consists of the load of his machine and his share in the machine’s activation cost. We prove that Nash equilibrium may not exist for the scheduling game. We design a polynomial-time algorithm to produce pareto-optimal schedules for two special cases of the scheduling game. Finally, we show that the general form of the scheduling game has pareto-optimal schedule by an improved polynomial-time algorithm, and prove that the schedule is a tight $𝜖$-approximate Nash equilibria.

This paper initializes distributed algorithm studies for core decomposition in probabilistic graphs. Core decomposition has been proven to be a useful primitive for a wide range of graph analyses, but it has rarely been studied in probabilistic graphs, especially in a distributed environment. In this work, under a distributed model underlying Pregel and live distributed systems, we present the first known distributed solutions for core decomposition in probabilistic graphs, where there is an existence probability for each edge. In the scenario that the existence probability of edges are known to nodes, the proposed algorithm can get the exact coreness of nodes with a high probability guarantee. The proposed algorithm can also be used to efficiently update the coreness of nodes in dynamic graphs, where a set of edges are inserted/deleted into/from the graph. In the harsher case that the existence probability is unknown, we present a novel method to estimate the existence probability of edges, based on which the coreness of nodes with small approximation ratio guarantee can be computed. Extensive experiments are conducted on different types of real-world graphs and synthetic graphs. The results illustrate that the proposed algorithms exhibit good efficiency, stability and scalability.

The problem of maximization submodular functions with a cardinality constraint has been extensively researched in recent years. Balkanski and Singer were the first to study this class problem. Subsequently, Chekuri and Kent recently extended these results to more general constraints, that is, $k$-cardinality constraint, partition and laminar matroids, matching, knapsack constraints, and including their intersection. They proposed a $(1-1/e-𝜀)$ approximation randomized-parallel-greedy algorithm which are poly-logarithmic adaptivity. However, these existing approaches are hardly extended to the nonsubmodular case. In this paper, we investigate the problem of maximization on a nonsubmodular function subject to a cardinality constraint, provided the objective function is specified by a generic submodularity ratio $\gamma$. We design a $(1-e^{-\gamma }-𝜀)$-approximation Greedy algorithm by using the technical aspects to maximize the multilinear relaxation of the object function under the $k$-cardinality constraints. The adaptive of multilinear relaxation is $O(logn/{𝜀}^2)$; the number of oracle is $Õ(n/{𝜀}^4)$.

In this paper, we propose a new non-smooth penalty function with two parameters for nonlinear inequality constrained optimization problems. And we propose a twice continuously differentiable function which is smoothing approximation to the non-smooth penalty function and define the corresponding smoothed penalty problem. A global solution of the smoothed penalty problem is proved to be an approximation global solution of the non-smooth penalty problem. Based on the smoothed penalty function, we develop an algorithm and prove that the sequence generated by the algorithm can converge to the optimal solution of the original problem.

Privacy-preserving empirical risk minimization model is crucial for the increasingly frequent setting of analyzing personal data, such as medical records, financial records, etc. Due to its advantage of a rigorous mathematical definition, differential privacy has been widely used in privacy protection and has received much attention in recent years of privacy protection. With the advantages of iterative algorithms in solving a variety of problems, like empirical risk minimization, there have been various works in the literature that target differentially private iteration algorithms, especially the adaptive iterative algorithm. However, the solution of the final model parameters is imprecise because of the vast privacy budget spending on the step size search. In this paper, we first proposed a novel adaptive differential privacy algorithm that does not require the privacy budget for step size determination. Then, through the theoretical analyses, we prove that our proposed algorithm satisfies differential privacy, and their solutions achieve sufficient accuracy by infinite steps. Furthermore, numerical analysis is performed based on real-world databases. The results indicate that our proposed algorithm outperforms existing algorithms for model fitting in terms of accuracy.

Finding vital vertices is an important issue in complex network analysis, which has wide applications in disease control, information diffusion, etc. This topic has attracted increasing attention from various disciplines. In this paper, we propose a new algorithm called Vertex–Edge algorithm to find vital vertices. This algorithm takes both the incident edges and also its neighbors into consideration when evaluating a vertex’s importance, and the importance of vertices and edges construct a mutually updated iterative framework. We also give convergence conditions for the iterative framework. Besides, we verify the stability, effectiveness, accuracy, and superiority of this new Vertex–Edge algorithm by applying it on lots of networks (unweighted or weighted) and comparing the results with other 10 more existing methods. This new method is expected to have promising applications in the future.

In this paper, we study the split equality fixed point problem and propose a new iterative algorithm with a self-adaptive stepsize that does not need the prior information of the operator norms and is calculated easily. The L-Lipschitz and quasi-pseudo-contractive mappings are chosen as the operators in the algorithm since they have a wider range of applications. Moreover, we prove that the sequence generated by the algorithm strongly converges to the solution of the problem. Finally, we check the feasibility and effectiveness of the algorithm by comparing with other algorithms.

In this paper, we study convex semi-infinite programming involving minimax problems. One of the difficulties in solving these problems is that the maximum type functions are not differentiable. Due to the nonsmooth nature of the problem, we apply the special proximal bundle scheme on the basis of ${𝒱}{𝒰}$-decomposition theory to solve the nonsmooth convex semi-infinite minimax problems. The proposed scheme requires an evaluation within some accuracy for all the components of the objective function. Regarding the incremental method, we only need one component function value and one subgradient which are estimated to update the bundle information and produce the search direction. Under some mild assumptions, we present global convergence and local superlinear convergence of the proposed bundle method. Numerical results of several example problems are reported to show the effectiveness of the new scheme.

In this paper, an advertising differential game model is proposed to describe the competition among different power retailers for attracting users in continuous time. After the equilibrium of advertising differential game is obtained, a multi-leader–multi-follower game model is developed to study the real-time pricing scheme in smart community. The power retailers calculate the optimal prices in response to the users’ power consumption and obtain the non-cooperation Nash equilibrium, and then the multi-leader–multi-follower game equilibrium is found. The numerical simulation is performed to discuss the influence of different factors on the payoff of power retailers and users and to verify the rationality of the proposed pricing scheme. The results show that both advertising efficiency and user scale have positive effects on the revenues of the power retailers. Besides, the rise of electricity price has negative effect on users’ utilities, meanwhile it makes the revenues of power retailers increase at first and then decrease. Moreover, power retailers will not transfer advertising costs to the users in the form of incremental electricity price.

Many flights experience delays at the airport due to bad weather, temporary closures of airports, unscheduled maintenance, etc., which emphasizes the urgent need for disruption management. It is widely accepted for Chinese airline companies to determine the flight timetable according to the lexicographic preference of flight priorities. Flight schedulers usually deal with the preceding flights as important as the latter flight of a higher priority. In this paper, we propose a build-in flight feasibility verification algorithm to improve the rescheduling algorithm. A novel model of the feasibility verification problem is given, which is equivalent to the model of a maximum clique problem for networks. Examples and tests show the advantage of our algorithm, and the algorithm runs fairly quickly and can be plugged in other scheduling algorithms easily.