Search

Let G = (V , E) be a graph. For an edge e = x y ∈ E , the closed neighbourhood of e, denoted by N G [ e ] or N G [ x y ] , is the set N G [ x ] ∪ N G [ y ] . A vertex set L ⊆ V is liar’s vertex-edge dominating set of a graph G = (V , E) if for every e i ∈ E , | N G [ e i ] ∩ L | ≥ 2 and for every pair of distinct edges e i and e j , | (N G [ e i ] ∪ N G [ e j ]) ∩ L | ≥ 3 . This paper introduces the notion of liar’s vertex-edge domination which arises naturally from some applications in communication networks. Given a graph G, the Minimum Liar’s Vertex-Edge Domination Problem (MinLVEDP) asks to find a liar’s vertex-edge dominating set of G of minimum cardinality. In this paper, we study this problem from an algorithmic point of view. We show that MinLVEDP can be solved in linear time for trees, whereas the decision version of this problem is NP-complete for general graphs, chordal graphs, and bipartite graphs. We further study approximation algorithms for this problem. We propose two approximation algorithms for MinLVEDP in general graphs and p-claw free graphs. On the negative side, we show that the MinLVEDP cannot be approximated within 1 2 (1 8 - ϵ) ln | V | for any ϵ > 0 , unless N P ⊆ D T I M E (| V | O (log (log | V |)) . Finally, we prove that the MinLVEDP is APX-complete for bounded degree graphs and p-claw-free graphs for p ≥ 6 . [ABSTRACT FROM AUTHOR]

Considering fairness has become increasingly important in recent research. This paper proposes the prize-collecting vertex cover problem with fairness constraints (FPCVC). In a prize-collecting vertex cover problem, those edges that are not covered incur penalties. By adding fairness concerns into the problem, the vertex set is divided into l groups, the goal is to find a vertex set to minimize the cost-plus-penalty value under the constraints that the profit of edges collected by each group exceeds a coverage requirement. In this paper, we propose a hybrid algorithm (combining deterministic rounding and randomized rounding) for the FPCVC problem which, with probability at least 1 - 1 / l α , returns a feasible solution with an objective value at most 9 (α + 1) 2 ln l + 3 times that of an optimal solution, where α is a constant. We also show a lower bound of Ω (ln l) for the approximability of FPCVC. Thus, our approximation ratio is asymptotically best possible. Experiments show that our algorithm performs fairly well empirically. [ABSTRACT FROM AUTHOR]

In this paper, we propose new algorithms for evacuation problems defined on dynamic flow networks. A dynamic flow network is a directed graph in which source nodes are given supplies and a single sink node is given a demand. The evacuation problem seeks a dynamic flow that sends all supplies from sources to the sink such that its demand is satisfied in the minimum feasible time horizon. For this problem, the current best algorithms are developed by Schlöter (2018) and Kamiyama (2019), which run in strongly polynomial time but with high-order polynomial time complexity because they use submodular function minimization as a subroutine. In this paper, we propose new algorithms that do not explicitly execute submodular function minimization, and we prove that they are faster than the current best algorithms when an input network is restricted such that the sink has a small in-degree and every edge has the same capacity. [ABSTRACT FROM AUTHOR]

A 3-star is a complete bipartite graph K 1 , 3 . A 3-star packing of a graph G is a collection of vertex-disjoint subgraphs of G in which each subgraph is a 3-star. The maximum 3-star packing problem is to find a 3-star packing of a given graph with the maximum number of 3-stars. A 2-independent set of a graph G is a subset S of V(G) such that for each pair of vertices u , v ∈ S , paths between u and v are all of length at least 3. In cubic graphs, the maximum 3-star packing problem is equivalent to the maximum 2-independent set problem. The maximum 2-independent set problem was proved to be NP-hard on cubic graphs (Kong and Zhao in Congressus Numerantium 143:65–80, 2000), and the best approximation algorithm of maximum 2-independent set problem for cubic graphs has approximation ratio 8 15 (Miyano et al. in WALCOM 2017, Proceedings, pp 228–240). In this paper, we first prove that the maximum 3-star packing problem is NP-hard in claw-free cubic graphs and then design a linear-time algorithm which can find a 3-star packing of a connected claw-free cubic graph G covering at least 3 v (G) - 8 4 vertices, where v(G) denotes the number of vertices of G. [ABSTRACT FROM AUTHOR]

More and more individuals are paying attention to the research on the emotional information found in micro-blog comments. TEXTCNN is growing rapidly in the short text space. However, because the training model of TEXTCNN model itself is not very extensible and interpretable, it is difficult to quantify and evaluate the relative importance of features and themselves. At the same time, word embedding can't solve the problem of polysemy at one time. This research suggests a microblog sentiment analysis method based on TEXTCNN and Bayes that addresses this flaw. First, the word embedding vector is obtained by word2vec tool, and based on the word vector, the ELMo word vector integrating contextual features and different semantic features is generated by ELMo model. Second, the local features of ELMo word vector are extracted from multiple angles by using the convolution layer and pooling layer of TEXTCNN model. Finally, the training task of emotion data classification is completed by combining Bayes classifier. On the Stanford Sentiment Classification Corpus data set SST (Stanford Sentiment Classification Corpus Data bank), the experimental findings demonstrate that the model in this paper is compared with TEXTCNN, LSTM, and LSTM–TEXTCNN models. The Accuracy, Precision, Recall, and F1-score of the experimental results of this research have all greatly increased. Their values are respectively 0.9813, 0.9821, 0.9804 and 0.9812, which are superior to other comparison models and can be effectively used for emotional accurate analysis and identification of events in microblog emotion analysis. [ABSTRACT FROM AUTHOR]

For the issue of carbon emission mitigation within the automotive supply chain, the cooperation between the vehicle manufacturers and the retailers has been proved to be an efficient measure to enhance emission reduction endeavors. This paper aims to evaluate the effectiveness of the cooperations between a vehicle manufacturer and multiple retailers based on the differential game method. By utilizing the Hamilton–Jacobi–Bellman equation, the equilibrium strategies of the participants under two different cooperation models, i.e., the decentralized model and the Stackelberg leader–follower cooperation model, are analyzed. To be specific, in the decentralized model, each participant independently decides its strategies, whereas the manufacturer cooperates with retailers by offering subsidies in the Stackelberg leader–follower model. Unlike previous studies that solely focused on participants’ decision-making in carbon emission reduction efforts, this paper also examines the retail pricing decisions of the retailers. Additionally, carbon trading is introduced to enhance the realism of our model. Through the theoretical analysis and the numerical experiments on the carbon emission reduction efforts of manufacturers and retailers, as well as the low-carbon reputation of vehicles and the overall system profit under both models, we conclude that the cooperative Stackelberg model outperforms the decentralized model in providing benefits to both parties. Furthermore, such a cooperative approach can foster the long-term development of the automotive supply chain, ultimately contributing to a more sustainable low-carbon future. [ABSTRACT FROM AUTHOR]

A graph that is isomorphic to the complete bipartite graph K 1 , r for some r ≥ 0 is called a star. A collection C = { V 1 , … , V k } of subsets of the vertex set of a graph G = (V , E) is called a star cover of G if each set in the collection induces a star and has V 1 ∪ … ∪ V k = V . A star cover C of a graph G = (V , E) is called a star partition of G if C is also a partition of V. The problem Star Cover takes a graph G as input and asks for a star cover of G of minimum size. The problem Star Partition takes a graph G as input and asks for a star partition of G of minimum size. From Shalu et al. (Discrete Appl Math 319:81–91, 2022), it follows that both these problems are NP-hard even for bipartite graphs. In this paper, we show that both Star Cover and Star Partition have O (n 7) time exact algorithms for double-split graphs. Proving that our algorithms indeed have running time Ω (n 7) necessitates the construction of an intricate infinite family of double-split graphs meeting several requirements. Other contributions of the paper are a simple linear time recognition algorithm for double-split graphs and a useful succinct matrix representation for double-split graphs. [ABSTRACT FROM AUTHOR]

An undirected graph G = (V , A) by a set V of n nodes, a set A of m edges, and two sets S , D ⊆ V consists of source and demand nodes are given. This paper presents two new versions of location problems which are called the f (σ) -location and g (σ) -location problems. We define an f (σ) -location of the network N as a node s ∈ S with the property that the maximum expense transmission time from the node s to the destinations of D is as cheap as possible. The f (σ) -location problem divides the range (0 , ∞) into intervals ∪ i (a i , b i) and finds a source s i ∈ S , for each interval (a i , b i) , such that s i is a f (σ) -location for each σ ∈ (a i , b i) . Also, define a g (σ) -location as a node s of S with the property that the sum of expense transmission times from the node s to all destinations of D is as cheap as possible. The g (σ) -location problem divides the range (0 , ∞) into intervals ∪ i (a i , b i) and finds a source s i ∈ S , for each interval (a i , b i) , such that s i is a g (σ) -location for each σ ∈ (a i , b i) . This paper presents two strongly polynomial time algorithms to solve f (σ) -location and g (σ) -location problems. [ABSTRACT FROM AUTHOR]

A (p, 1)-total labelling of a graph G is a mapping f: V (G) ∪ E (G) → { 0 , 1 , ⋯ , k } such that | f (u) - f (v) | ≥ 1 if u v ∈ E (G) , | f (e 1) - f (e 2) | ≥ 1 if e 1 and e 2 are two adjacent edges in G and | f (u) - f (e) | ≥ p if the vertex u is incident with the edge e. In this paper, we focus on the list version of a (p, 1)-total labelling. Given a family L = { L (u) ⊆ N : u ∈ V (G) ∪ E (G) } , an L-list (p, 1)-total labelling of G is a (p, 1)-total labelling f of G such that f (u) ∈ L (u) for every element u ∈ V (G) ∪ E (G) . A graph G is said to be (p, 1)-k-total choosable if it admits an L-list (p, 1)-total labelling whenever the family L contains only sets of size at least k. The smallest k for which a graph G is (p, 1)-k-total choosable is the list (p, 1)-total labelling number of G, denoted by λ lp T (G) . In this paper, we firstly use some important theorems related to Combinatorial Nullstellensatz to prove that the upper bound of λ lp T (C n) for cycles C n is 2 p + 1 with p ≥ 2 . Let G be a graph with maximum degree Δ (G) ≥ 6 p + 3 . Then we prove that if G is a planar graph or a 1-planar graph without adjacent 3-cycles, then λ lp T (G) ≤ Δ (G) + 2 p - 1 ( p ≥ 2 ). [ABSTRACT FROM AUTHOR]

This paper introduces an integer linear program for a variant of the linear ordering problem. This considers, besides the pairwise preferences in the objective function as the linear ordering problem, positional preferences (weighted rank) in the objective. The objective function is mathematically supported, as the full integer linear program is motivated by the instant run-off voting method to aggregate individual preferences. The paper describes two meta-heuristics, iterated local search and Memetic algorithms to deal with large instances which are hard to solve to optimality. These results are compared with the objective value of the linear relaxation. The instances used are the ones available from the LOP library, and new real instances with preferences given by juries. [ABSTRACT FROM AUTHOR]

In this paper, we investigate the minimum resolving dominating set problem which is a emerging combinatorial optimization problem in general graphs. We prove that the resolving dominating set problem is NP-hard and propose a greedy algorithm with an approximation ratio of ( 1 + 2 ln n ) by establishing a submodular potential function, where n is the node number of the input graph. [ABSTRACT FROM AUTHOR]

We study the fashion game, a classical network coordination/anti-coordination game employed to model social dynamics in decision-making processes, especially in fashion choices. In this game, individuals, represented as vertices in a graph, make decisions based on their neighbors’ choices. Some individuals are positively influenced by their neighbors while others are negatively affected. Analyzing the game’s outcome aids in understanding fashion trends and flux within the population. In an instance of the fashion game, an action profile is formed when all individuals have made their choices. The utility of an individual under an action profile is defined according to the choices he and his neighbors made. A pure Nash equilibria is an action profile under which each individual has a nonnegative utility. To further study the existence of pure Nash equilibria, we investigate an associated optimization problem aimed at maximizing the minimal individual utility, referred to as the utility of a fashion game instance. The fashion game with two different but symmetric actions (choices) has been studied extensively in the literature. This paper seeks to extend the fashion game analysis to scenarios with more than two available actions, thereby enhancing comprehension of social dynamics in decision-making processes. We determine the utilities of all instances on paths, cycles and complete graphs. For instances where each individual likes to anti-coordinate, graph is planar and three actions are available, we illustrate the time complexity of determining the utility of such instances. Additionally, for instances containing both coordinating and anti-coordinating individuals, we extend the results on the time complexity of determining the utility of instances with two available actions to cases with more than two actions. [ABSTRACT FROM AUTHOR]

This paper presents theoretical and practical results for the bin packing problem with scenarios, a generalization of the classical bin packing problem which considers the presence of uncertain scenarios, of which only one is realized. For this problem, we propose approximation algorithms whose ratios are bounded by the square root of the number of scenarios times the approximation ratio for an algorithm for the vector bin packing problem. We also show how an asymptotic polynomial-time approximation scheme is derived when the number of scenarios is constant, that is, not a part of the input. As a practical study of the problem, we present a branch-and-price algorithm to solve an exponential set-cover model and a variable neighborhood search heuristic. Experiments show the competence of the branch-and-price in obtaining optimal solutions for about 59% of the instances considered, while the combined heuristic and branch-and-price optimally solved 62% of the instances considered. [ABSTRACT FROM AUTHOR]

A mixed dominating set in a graph G = (V , E) is a subset D of vertices and edges of G such that every vertex and edge in (V ∪ E) \ D is a neighbor of some elements in D. The mixed domination number of G, denoted by γ md (G) , is the minimum size among all mixed dominating sets of G. For natural numbers n and k, where n > 2 k , a generalized Petersen graph P(n, k) is a graph with vertices { v 0 , v 1 , … , v n - 1 } ∪ { u 0 , u 1 , … , u n - 1 } and edges ∪ 0 ≤ i ≤ n - 1 { v i v i + 1 , v i u i , u i u i + k } where subscripts are modulo n. In this paper, we explicitly construct an optimal mixed dominating set for generalized Petersen graphs P(n, k) for k ∈ { 1 , 2 } . Moreover, we establish some upper bound on mixed domination number for other generalized Petersen graphs. [ABSTRACT FROM AUTHOR]

Given a monotone submodular set function with a knapsack constraint, its maximization problem has two types of approximation algorithms with running time O (n 2) and O (n 5) , respectively. With running time O (n 5) , the best performance ratio is 1 - 1 / e . With running time O (n 2) , the well-known performance ratio is (1 - 1 / e) / 2 and an improved one is claimed to be (1 - 1 / e 2) / 2 recently. In this paper, we design an algorithm with running O (n 2) and performance ratio 1 - 1 / e 2 / 3 , and an algorithm with running time O (n 3) and performance ratio 1/2. [ABSTRACT FROM AUTHOR]

Budget games were introduced by Drees, Riechers, and Skopalik (2014) as a model of noncooperative games arising from resource allocation problems. Budget games have several similarities to congestion games, one of which is that the matroid structure of the strategy space is essential for the existence of a pure Nash equilibrium (PNE). Despite these similarities, however, the theoretical relation between budget games and congestion games has been unclear. In this paper, we provide a common generalization of budget games and congestion games, called generalized budget games (g-budget games, for short), to establish a large class of noncooperative games retaining the nice property of the matroid structure. We show that the model of g-budget games includes weighted congestion games and player-specific congestion games under certain assumptions. We further show that g-budget games also include offset budget games, a generalized model of budget games by Drees, Feldotto, Riechers, and Skopalik (2019). We then prove that every matroid g-budget game has a PNE, which extends the result for budget games. We finally a PNE in a certain class of singleton g-budget games can be computed in a greedy manner. [ABSTRACT FROM AUTHOR]

In this paper, we consider the W-prize-collecting scheduling problem on parallel machines. In this problem, we are given a set of n jobs, a set of m identical parallel machines and a value W. Each job J j has a processing time, a profit and a rejection penalty. Each job is either accepted and processed on one of the machines without preemption, or rejected and paid a rejection penalty. The objective is to minimize the sum of the makespan of accepted jobs and the penalties of rejected jobs, and at the same time the total profit brought by accepted jobs is not less than W. We design a 2-approximation algorithm for the problem based on the greedy method and the list scheduling algorithm. [ABSTRACT FROM AUTHOR]

A floorplan (F) is a partition of a polygonal boundary (P) into n-regions satisfying the adjacencies given by an n-vertex graph. Here, it is assumed that the sides of the polygonal boundary are either parallel to the x-axis or y-axis or have slopes - 1 or 1. For a given polygonal boundary P (having m line segments) and a plane triangulated graph G, this paper presents a linear-time algorithm for constructing a floorplan with the required polygonal boundary satisfying all given adjacencies. Further, it has been proved that the number of sides of each region in the obtained floorplan (F) is at most m + 1 (except one region, which can have at most m + 5 sides) for the given polygonal boundary P of length m. [ABSTRACT FROM AUTHOR]

In this paper, we address the trip-constrained vehicle routing cover problem (the TcVRC problem). Specifically, given a metric complete graph G = (V , E ; w) with a set D (⊆ V) of depots, a set J (= V \ D) of customer locations, each customer having unsplittable demand 1, and k vehicles with capacity Q, it is asked to find a set C = { C i | i = 1 , 2 , … , k } of k tours for k vehicles to service all customers, each tour for a vehicle starts and ends at one depot in D and permits to be replenished at some other depots in D before continuously servicing at most Q customers, i.e., the number of customers continuously serviced in per trip of each tour is at most Q (except the two end-vertices of that trip), where each trip is a path or cycle, starting at a depot and ending at other depot (maybe the same depot) in D, such that there are no other depots in the interior of that path or cycle, the objective is to minimize the maximum weight of such k tours in C , i.e., min C max { w (C i) | i = 1 , 2 , … , k } , where w (C i) is the total weight of edges in that tour C i . Considering k vehicles whether to have common depot or suppliers, we consider three variations of the TcVRC problem, i.e., (1) the trip-constrained vehicle routing cover problem with multiple suppliers (the TcVRC-MS problem) is asked to find a set C = { C i | i = 1 , 2 , … , k } of k tours mentioned-above, the objective is to minimize the maximum weight of such k tours in C ; (2) the trip-constrained vehicle routing cover problem with common depot and multiple suppliers (the TcVRC-CDMS problem) is asked to find a set C = { C i | i = 1 , 2 , … , k } of k tours mentioned-above, where each tour starts and ends at same depot v in D, each vehicle having its suppliers at some depots in D (possibly including v), the objective is to minimize the maximum weight of such k tours in C ; (3) the trip-constrained k-traveling salesman problem with non-suppliers (the TckTS-NS problem, simply the TckTSP-NS) is asked to find a set C = { C i | i = 1 , 2 , … , k } of k tours mentioned-above, where each tour starts and ends at same depot v in D, each vehicle having non-suppliers, the objective is to minimize the maximum weight of such k tours in C . As for the main contributions, we design some approximation algorithms to solve these three aforementioned problems in polynomial time, whose approximation ratios achieve three constants 8 - 2 k , 7 2 - 1 k and 5, respectively. [ABSTRACT FROM AUTHOR]

This paper addresses the minmax regret 1-sink location problem on a dynamic flow path network with parametric weights. A dynamic flow path network consists of an undirected path with positive edge lengths, positive edge capacities, and nonnegative vertex weights. A path can be considered as a road, an edge length as the distance along the road, and a vertex weight as the number of people at the site. An edge capacity limits the number of people that can enter the edge per unit time. We consider the problem of locating a sink where all the people evacuate quickly. In our model, each weight is represented by a linear function of a common parameter t, and the decision maker who determines the sink location does not know the value of t. We formulate the problem under such uncertainty as the minmax regret problem. Given t and sink location x, the cost is the sum of arrival times at x for all the people determined by t. The regret for x under t is the gap between this cost and the optimal cost under t. The problem is to find the sink location minimizing the maximum regret over all t. For the problem, we propose an O (n 4 2 α (n) α (n) 2 log n) time algorithm, where n is the number of vertices in the network and α (·) is the inverse Ackermann function. Also, for the special case in which every edge has the same capacity, we show that the complexity can be reduced to O (n 3 2 α (n) α (n) log n) . [ABSTRACT FROM AUTHOR]

Gromov–Hausdorff distances measure shape difference between the objects representable as compact metric spaces, e.g. point clouds, manifolds, or graphs. Computing any Gromov–Hausdorff distance is equivalent to solving an NP-hard optimization problem, deeming the notion impractical for applications. In this paper we propose a polynomial algorithm for estimating the so-called modified Gromov–Hausdorff (mGH) distance, a relaxation of the standard Gromov–Hausdorff (GH) distance with similar topological properties. We implement the algorithm for the case of compact metric spaces induced by unweighted graphs as part of Python library scikit-tda, and demonstrate its performance on real-world and synthetic networks. The algorithm finds the mGH distances exactly on most graphs with the scale-free property. We use the computed mGH distances to successfully detect outliers in real-world social and computer networks. [ABSTRACT FROM AUTHOR]

In this paper, we consider the following two-machine no-wait flow shop scheduling problem with two competing agents F 2 | M 1 → M 2 , M 2 , p ij A = p , n o - w a i t | C max A : C max B ≤ Q : Given a set of n jobs J = { J 1 , J 2 , … , J n } and two competing agents A and B. Agent A is associated with a set of n A jobs J A = { J 1 A , J 2 A , … , J n A A } to be processed on the machine M 1 first and then on the machine M 2 with no-wait constraint, and agent B is associated with a set of n B jobs J B = { J 1 B , J 2 B , … , J n B B } to be processed on the machine M 2 only, where the processing times for the jobs of agent A are all the same (i.e., p ij A = p ), J = J A ∪ J B and n = n A + n B . The objective is to build a schedule π of the n jobs that minimizing the makespan of agent A while maintaining the makespan of agent B not greater than a given value Q. We first show that the problem is polynomial time solvable in some special cases. For the non-solvable case, we present an O (n log n) -time (1 + 1 n A + 1) -approximation algorithm and show that this ratio of (1 + 1 n A + 1) is asymptotically tight. Finally, (1 + ϵ) -approximation algorithms are provided. [ABSTRACT FROM AUTHOR]

With the advancement of electronic service platforms, customers exhibit various purchasing behaviors. Given the extensive array of options and minimal exit barriers, customer migration from one digital service to another has become a common challenge for businesses. Customer churn prediction (CCP) emerges as a crucial marketing strategy aimed at estimating the likelihood of customer abandonment. In this paper, we aim to predict customer churn intentions using a novel robust meta-classifier. We utilized three distinct datasets: transaction, telecommunication, and customer churn datasets. Employing Decision Tree, Random Forest, XGBoost, AdaBoost, and Extra Trees as the five base supervised classifiers on these three datasets, we conducted cross-validation and evaluation setups separately. Additionally, we employed permutation and SelectKBest feature selection to rank the most practical features for achieving the highest accuracy. Furthermore, we utilized BayesSearchCV and GridSearchCV to discover, optimize, and tune the hyperparameters. Subsequently, we applied the refined classifiers in a funnel of a new meta-classifier for each dataset individually. The experimental results indicate that our proposed meta-classifier demonstrates superior accuracy compared to conventional classifiers and even stacking ensemble methods. The predictive outcomes serve as a valuable tool for businesses in identifying potential churners and taking proactive measures to retain customers, thereby enhancing customer retention rates and ensuring business sustainability. [ABSTRACT FROM AUTHOR]

This paper concerns online portfolio selection problem whose main feature is with no any statistical assumption on future asset prices. Since online portfolio selection aims to maximize the cumulative wealth, most existing online portfolio strategies do not consider risk factors into the model. To enrich the research on online portfolio selection, we introduce the risk factors into the model and propose two novel risk-adjusted online portfolio strategies. More specifically, we first choose several exponentialgradient ( EG (η) ) with different values of parameter η to build an expert pool. Later, we construct two risk methods to measure performance of each expert. Finally, we calculate the portfolio by the weighted average over all expert advice. We present theoretical and experimental results respectively to analyze the performance of the proposed strategies. Theoretical results show that the proposed strategies not only track the expert with the lowest risk, but also are universal, i.e., they exhibit the same asymptotic average logarithmic growth rate as bestconstantrebalancedportfolio (BCRP) determined in hindsight. We conduct extensive experiments by using daily stock data collected from the American and Chinese stock markets. Experimental results show the proposed strategies outperform existing online portfolio in terms of the return and risk metrics in most cases. [ABSTRACT FROM AUTHOR]

In this paper, we address an extension of the classical two-dimensional bin packing (2BPP) that considers the spread of customer orders (2BPP-OS). The 2BPP-OS addresses a set of rectangular items, required from different customer orders, to be cut from a set of rectangular bins. All the items of a customer order are dispatched together to the next stage of production or distribution after its completion. The objective is to minimize the number of bins used and the spread of customer orders over the cutting process. The 2BPP-OS gains relevance in manufacturing environments that seek minimum waste solutions with satisfactory levels of customer service. We propose integer linear programming (ILP) models for variants of the 2BPP-OS that consider non-guillotine, 2-stage, restricted 3-stage, and unrestricted 3-stage patterns. We are not aware of integrated approaches for the 2BPP-OS in the literature despite its relevance in practical settings. Using a general-purpose ILP solver, the results show that the 2BPP-OS takes more computational effort to solve than the 2BPP, as it has to consider several symmetries that are often disregarded by the traditional 2BPP approaches. The solutions obtained by the proposed approaches have similar bin usage and significantly better metrics of customer satisfaction concerning the approaches that neglect the customer order spread. [ABSTRACT FROM AUTHOR]

Low-Acy-Matching asks to find a maximal matching M in a given graph G of minimum cardinality such that the set of M-saturated vertices induces an acyclic subgraph in G. The decision version of Low-Acy-Matching is known to be NP -complete. In this paper, we strengthen this result by proving that the decision version of Low-Acy-Matching remains NP -complete for bipartite graphs with maximum degree 6 and planar perfect elimination bipartite graphs. We also show the hardness difference between Low-Acy-Matching and Max-Acy-Matching. Furthermore, we prove that, even for bipartite graphs, Low-Acy-Matching cannot be approximated within a ratio of n 1 - ϵ for any ϵ > 0 unless P = NP . Finally, we establish that Low-Acy-Matching exhibits APX -hardness when restricted to 4-regular graphs. [ABSTRACT FROM AUTHOR]

The Probabilistic p-Center problem under Pressure (Min PpCP) is a variant of the usual Minp-Center problem we recently introduced in the context of wildfire management. The problem is to locate p shelters minimizing the maximum distance people will have to cover in case of fire in order to reach the closest accessible shelter. The landscape is divided into zones and is modeled as an edge-weighted graph with vertices corresponding to zones and edges corresponding to direct connections between two adjacent zones. The risk associated with fire outbreaks is modeled using a finite set of fire scenarios. Each scenario corresponds to a fire outbreak on a single zone (i.e., on a vertex) with the main consequence of modifying evacuation paths in two ways. First, an evacuation path cannot pass through the vertex on fire. Second, the fact that someone close to the fire may not take rational decisions when selecting a direction to escape is modeled using new kinds of evacuation paths. In this paper, we characterize the set of feasible solutions of Min PpCP-instance. Then, we propose some approximation results for Min PpCP. These results require approximation results for two variants of the (deterministic) Minp-Center problem called Min MACp-Center and Min Partialp-Center. [ABSTRACT FROM AUTHOR]

The online graph exploration problem, which was proposed by Kalyanasundaram and Pruhs (Theor Comput Sci 130(1):125–138, 1994), is defined as follows: Given an edge-weighted undirected connected graph and a specified vertex (called the origin), the task of an algorithm is to compute a path from the origin to the origin which contains all the vertices of the given graph. The goal of the problem is to find such a path of minimum weight. At each time, an online algorithm knows only the weights of edges each of which consists of visited vertices or vertices adjacent to visited vertices. Fritsch (Inform Process Lett 168:1006096, 2021) showed that the competitive ratio of an online algorithm is at most three for any unicyclic graph. On the other hand, Brandt et al. (Theor Comput Sci 839:176–185, 2020) showed a lower bound of two on the competitive ratio for any unicyclic graph. In this paper, we showed the competitive ratio of an online algorithm is at most 5/2 for any unicyclic graph. [ABSTRACT FROM AUTHOR]

Göring–Helmberg–Wappler introduced optimization problems regarding embeddings of a graph into a Euclidean space and the first nonzero eigenvalue of the Laplacian of a graph, which are dual to each other in the framework of semidefinite programming. In this paper, we introduce a new graph-embedding optimization problem, and discuss its relation to Göring–Helmberg–Wappler's problems. We also identify the dual problem to our embedding optimization problem. We solve the optimization problems for distance-regular graphs and the one-skeleton graphs of the C 60 fullerene and some other Archimedian solids. [ABSTRACT FROM AUTHOR]

The minimum connected dominating set problem is widely studied due to its applicability to mobile ad-hoc networks and sensor grids. Its variant the minimum 2-connected dominating set (M-2CDS) problem has become increasingly important because its critical role in designing fault-tolerant network. This paper presents a connected dominating degree-based local search (CDD-LS) tailored for solving the M-2CDS. The proposed algorithm implements an improved swap-based neighborhood structure as well as the corresponding fast neighborhood evaluation method using connected dominating degree data structure. The diversification techniques including tabu strategy and perturbaistion help the search jump out of the local optima improving the efficiency. This study investigates the performance of the CDD-LS algorithm on 38 publicly available benchmark datasets. The results demonstrate that the CDD-LS algorithm significantly improves the best runtime in 19 instances, while providing the equivalent performance in 8 instances. Furthermore, the CDD-LS is tested on 18 newly generated instances to check its capability on large-scale scenarios. To gain a deeper understanding of the algorithm’s effectiveness, an investigation into the key components of the CDD-LS algorithm is conducted. [ABSTRACT FROM AUTHOR]

This paper tackles the two-machine chain-reentrant flow shop scheduling problem with the no-wait constraint; we assume that each job passes from the first machine to the second and returns back to the first machine in order to execute its last operation. The objective is to minimize the makespan. In this work, we prove that the symmetric case of this problem, which is proven to be N P -hard in the strong sense, remains N P -hard. Then we provide two polynomial subproblems. For the main problem’s resolution, we propose two new efficient heuristics as well as two improved lower bounds that consistently outperform the existing methods. Additionally, we provide an effective Branch & Bound algorithm that can solve up to 100 jobs for some types of instances. These contributions not only enhance the theoretical comprehension of the problem but also offer efficient solutions supported by extensive statistical analysis over randomly generated instances. [ABSTRACT FROM AUTHOR]

The problem studied in this paper is elective surgery scheduling, with resource constraints in each of the three following stages: preoperative, perioperative, and postoperative stages. With the integrated availability of hospital beds in wards and operating rooms, the aim is to determine operation start times of surgeries and allocate the hospital beds to patients while getting patients treated as soon as possible. This task is crucial in providing timely treatments for the patients while ensuring the hospital’s resource utilization balance. For the problem, we first formulate it as mixed-integer programming, which is NP-complete. Then, we propose several heuristics to overcome the long computation time. To make the solution better, we also propose improved algorithms. Finally, we conduct a series of numerical studies to illustrate the efficiency of our proposed algorithms and examine the impact of the number of jobs, beds, and surgery blocks on the performance measure. Computational experiments showed the superior performance of our heuristics in makespan. [ABSTRACT FROM AUTHOR]

The online optimization model was first introduced in the research of machine learning problems (Zinkevich, Proceedings of ICML, 928–936, 2003). It is a powerful framework that combines the principles of optimization with the challenges of online decision-making. The present research mainly consider the case that the reveal objective functions are convex or submodular. In this paper, we focus on the online maximization problem under a special objective function Φ (x) : [ 0 , 1 ] n → R + which satisfies the inequality 1 2 ⟨ u T ∇ 2 Φ (x) , u ⟩ ≤ σ · ‖ u ‖ 1 ‖ x ‖ 1 ⟨ u , ∇ Φ (x) ⟩ for any x , u ∈ [ 0 , 1 ] n , x ≠ 0 . This objective function is named as one sided σ -smooth (OSS) function. We achieve two conclusions here. Firstly, under the assumption that the gradient function of OSS function is L-smooth, we propose an (1 - exp ((θ - 1) (θ / (1 + θ)) 2 σ)) - approximation algorithm with O (T) regret upper bound, where T is the number of rounds in the online algorithm and θ , σ ∈ R + are parameters. Secondly, if the gradient function of OSS function has no L-smoothness, we provide an 1 + ((θ + 1) / θ) 4 σ - 1 -approximation projected gradient algorithm, and prove that the regret upper bound of the algorithm is O (T) . We think that this research can provide different ideas for online non-convex and non-submodular learning. [ABSTRACT FROM AUTHOR]

Grey wolf optimizer (GWO) is one of the most popular metaheuristics, and it has been presented as highly competitive with other comparison methods. However, the basic GWO needs some improvement, such as premature convergence and imbalance between exploitation and exploration. To address these weaknesses, this paper develops a hybrid grey wolf optimizer (HGWO), which combines the Halton sequence, dimension learning-based, crisscross strategy, and Cauchy mutation strategy. Firstly, the Halton sequence is used to enlarge the search scope and improve the diversity of the solutions. Then, the dimension learning-based is used for position update to balance exploitation and exploration. Furthermore, the crisscross strategy is introduced to enhance convergence precision. Finally, the Cauchy mutation strategy is adapted to avoid falling into the local optimum. The effectiveness of HGWO is demonstrated by comparing it with advanced algorithms on the 15 benchmark functions in different dimensions. The results illustrate that HGWO outperforms other advanced algorithms. Moreover, HGWO is used to solve eight real-world engineering problems, and the results demonstrate that HGWO is superior to different advanced algorithms. [ABSTRACT FROM AUTHOR]

An injective edge-coloring of a graph G is an edge-coloring of G such that any two edges that are at distance 2 or in a common triangle receive distinct colors. The injective chromatic index of G is the minimum number of colors needed to guarantee that G admits an injective edge-coloring. Ferdjallah, Kerdjoudj and Raspaud showed that the injective chromatic index of every subcubic graph is at most 8, and conjectured that 8 can be improved to 6. Kostochka, Raspaud and Xu further proved that every subcubic graph has the injective chromatic index at most 7, and every subcubic planar graph has the injective chromatic index at most 6. In this paper, we consider the injective edge-coloring of claw-free subcubic graphs. We show that every connected claw-free subcubic graph, apart from two exceptions, has the injective chromatic index at most 5. We also consider the list version of injective edge-coloring and prove that the list injective chromatic index of every claw-free subcubic graph is at most 6. Both results are sharp and strengthen a recent result of Yang and Wu which asserts that every claw-free subcubic graph has the injective chromatic index at most 6. [ABSTRACT FROM AUTHOR]

Given a strongly connected mixed graph G = (V , E , A) , where V represents the vertex set, E is the undirected edge set, and A is the directed arc set, R ⊆ E is a subset of required edges and is divided into p clusters R 1 , R 2 , ⋯ , R p , and A is a set of required arcs and is partitioned into q clusters A 1 , A 2 , … , A q . Each edge in E and each arc in A are associated with a nonnegative weight and the weight function satisfies the triangle inequality. In this paper we consider two clustered arc routing problems. The first is the Clustered Rural Postman Problem, in which A is empty and the objective is to find a minimum-weight closed walk such that all the edges in R are serviced and the edges in R i ( 1 ≤ i ≤ p ) are serviced consecutively. The other is the Clustered Stacker Crane Problem, in which R is empty and the goal is to find a minimum-weight closed walk that traverses all the arcs in A and services the arcs in A j ( 1 ≤ j ≤ q ) consecutively. For both problems, we propose constant-factor approximation algorithms with ratios 13/6 and 19/6, respectively. [ABSTRACT FROM AUTHOR]

Lattice is the main research subject in the geometry of numbers. SVP refers to finding a shortest nonzero lattice vector in a given lattice, which is thought to be a difficult optimization problem. For general lattice, the integer coefficients of a shortest nonzero vector under a lattice basis might be exponentially large, thus making the simple integer coefficient searching approach impractical. In this paper, we find that for low-dimensional circulant lattices(dimension n ∈ { 2 , 3 , 4 , 6 } ), the integer coefficients of a shortest lattice vector under its circulant basis are actually in a small set S = { - 1 , 0 , 1 } , which makes it easy to find the shortest vector in these cases. Moreover, we present the specific forms of the SVP solutions for low-dimensional circulant lattices. [ABSTRACT FROM AUTHOR]

Gene trees inferred from molecular sequence alignments are typically unrooted, and determining the most credible rooting edge is a classical problem in computational biology. One approach to solve this problem is unrooted reconciliation, where the rooting edge is postulated based on the split of the root from a given species tree. In this paper, we propose a novel variant of the gene tree rooting problem, where the gene tree root is inferred using a phylogenetic network of the species present in the gene tree. To obtain the best rooting, unrooted reconciliation can be applied, where the unrooted gene tree is jointly reconciled with a set of splits inferred from the network. However, the exponential size of the set induced by display trees of the network makes this approach computationally prohibitive. To address this, we propose a broader and easier-to-control set of splits based on the structural properties of the network. We then derive exact mathematical formulas for the rooting problem and propose two general rooting algorithms to handle cases where the input network does not meet the initial requirements. Our experimental study based on simulated gene trees and networks demonstrates that our algorithms infer gene tree rootings correctly or with a small error in most cases. [ABSTRACT FROM AUTHOR]

Diabetes is regarded as one of the deadliest chronic illnesses that increases blood sugar. But there is no reliable method for predicting diabetic severity that shows how the disease will affect various body organs in the future. Therefore, this paper introduced Optimized Dual Directional Temporal convolution and Attention based Density Clustering (ODDTADC) method for predicting and classifying risk level in diabetic patients. In the diabetic prediction stage, the prediction is done by using an Integrated Dual Directional Temporal Convolution and an Enriched Remora Optimization Algorithm. Here, dual directional temporal convolution is used to extract temporal features by integrating dilated convolution and casual convolution in the feature extraction layer. Then, the attention module is used instead of max-pooling to emphasize the various features' importance in the feature aggregation layer. The Enriched Remora Optimization Algorithm is used to find optimal hyper parameters for Integrated Dual Directional Temporal Convolution. In the classification of stages based on risk level, the values from stage-I are fed into the Attention based Density Spatial Clustering of Applications with Noise, which allocate various weights based on their density values in the Core Points. Based on the results, the Nested Long Short-Term Memory is utilized to classify the risk levels of diabetic patients over a period of two or three years. Experimental evaluations were performed on five datasets, including PIMA Indian Diabetics Database, UCI Machine Learning Repository Diabetics Dataset, Heart Diseases Dataset, Chronic Disease Dataset and Diabetic Retinopathy Debrecen Dataset. The proposed ODDTADC method demonstrates superior performance compared to existing methods, achieving remarkable results in accuracy (98.21%), recall (94.46%), kappa coefficient (98.95%), precision (98.74%), F1-score (99.01%) and Matthew’s correlation coefficient (MCC) (0.87%). [ABSTRACT FROM AUTHOR]

The diameter of an undirected or a directed graph is defined to be the maximum shortest path distance over all pairs of vertices in the graph. Given an undirected graph G, we examine the problem of assigning directions to each edge of G such that the diameter of the resulting oriented graph is minimized. The minimum diameter over all strongly connected orientations is called the oriented diameter of G. The problem of determining the oriented diameter of a graph is known to be NP-hard, but the time-complexity question is open for planar graphs. In this paper we compute the exact value of the oriented diameter for triangular grid graphs. We then prove an n/3 lower bound and an n / 2 + O n upper bound on the oriented diameter of planar triangulations, where n is the number of vertices in G. It is known that given a planar graph G with bounded treewidth and a fixed positive integer k, one can determine in linear time whether the oriented diameter of G is at most k. We consider a weighted version of the oriented diameter problem and show it to be weakly NP-complete for planar graphs with bounded pathwidth. [ABSTRACT FROM AUTHOR]

An autonomous robot with a limited vision range finds a path to the goal in an unknown environment in 2D avoiding polygonal obstacles. In the process of discovering the environmental map, the robot has to return to some positions marked previously, the regions where the robot traverses to reach that position are defined as sequences of bundles of line segments. This paper presents a novel algorithm for finding approximately shortest paths along the sequences of bundles of line segments based on the method of multiple shooting. Three factors of the approach including bundle partition, collinear condition, and update of shooting points are presented. We then show that if the collinear condition holds, the exact shortest path of the problem is determined, otherwise, the sequence lengths of paths obtained by the update of the method converges. The algorithm is implemented in Python and some numerical examples show that the running time of path-planing for autonomous robots using our method is faster than that using the rubber band technique of Li and Klette in Euclidean Shortest Paths, Springer, 53–89 (2011). [ABSTRACT FROM AUTHOR]

To explore the influencing factors of living energy consumption, this paper studies the carbon emissions of living energy consumption, and combines the spatiotemporal model to analyze the influencing factors of living energy consumption and carbon emissions. Moreover, this paper proposes a new carbon emission anomaly trajectory detection algorithm STOD for detecting spatiotemporal anomalies. The algorithm segments the complete carbon emission spatiotemporal trajectory and merges the carbon emission trajectory segments that meet the conditions according to the definition. In addition, this paper obtains the abnormal trajectory segment and abnormal trajectory of carbon emissions by calculating three different metrics. The proposed model obtains the outcome of 91.45 during the evaluation of living energy consumption carbon emission analysis based on the spatiotemporal model. The experimental study shows that the carbon emission analysis based on the spatiotemporal model proposed in this paper has a better effect. [ABSTRACT FROM AUTHOR]

With the development of the Internet of Things and the emergence of various computing paradigms, the use of social networks has become more diverse and data has exploded, making users more sensitive to the access delay of various new media when using social media. To meet the demand of massive data processing and users' access delay, edge-cloud computing—a new computing paradigm combining cloud computing and edge computing- starts to provide users with data storage and processing services. The popularity and convenience of smart devices, with hundreds of millions of users using social networking apps on their smart devices, has led to an explosion in the amount of data generated by the devices. However, in the edge-cloud environment, there is no trust mechanism between multilayer resource nodes. How to maintain the load balance of data storage to ensure the system performance becomes increasingly important. To solve the above problems, based on GP algorithm, a secure data placement model of edge-cloud computing is proposed under the constraints of ensuring user access delay and load balance. In this paper, real datasets are used for simulation experiments, and the experimental results show that the proposed algorithm has good performance. [ABSTRACT FROM AUTHOR]

In the post-COVID-19 period, the regional economic development gap in Guangdong has expanded and the risk has increased. This is not conducive to building a well-off society in Guangdong in an all-round way. Optimizing the industrial structure, changing the mode of economic growth, preventing regional economic risks, and narrowing the regional economic development gap are the focus of Guangdong governments at all levels. Based on a two-sector economic growth model, the paper uses descriptive statistics and Deng's grey correlation method to analyze the economic development panel data of 21 prefecture-level cities of Guangdong Province from 2011 to 2018, analyzes the characteristics of regional economic development in Guangdong, and makes experimental research of the effect of industrial structure optimization and economic development factors on economic growth in Guangzhou, Zhongshan, Shantou, Maoming and Meizhou at different stages of development. The results show that: there are differences in the industrial structure and the level of economic development in different regions; the rationalization of industrial structure and upgrading of the industrial structure has an impact on economic growth and show different features during different stages; in different stages of economic development, foreign trade, scientific and technological innovation are the main factors affecting regional economic growth. This paper holds that the northwest of Guangdong Province and the Pearl River Delta should formulate industrial structure adjustment policies to promote the rationalization of regional industrial structure, expand foreign trade channels and innovate financing mechanisms, and restrain regional economic risks in combination with regional characteristics. The new development pattern of domestic and international dual circulation and mutual promotion, further expands the level of opening up, effectively playing the role of free trade pilot areas, free trade ports, special economic zones, development zones, bonded areas, and other frontier highlands, improve the level and capacity of foreign trade. [ABSTRACT FROM AUTHOR]

Professional clothing design for high-temperature operations is an essential concern for industrial development. In this paper, for the existing layering of professional garments for high-temperature operations, the finite difference method is used to establish the model for the internal temperature variation of the garments. A multi-objective model is established to optimize the layering thickness of the existing professional garments for high-temperature operations. Finally, considering the heat transfer in its actual operating environment, the boundary conditions of its data model are optimized to provide a feasible solution for the subsequent design and development of high-temperature operating clothing and apparatus. [ABSTRACT FROM AUTHOR]

In this paper, we propose a physical protocol to verify the first nonzero term of a sequence using a deck of cards. The protocol lets a prover show the value of the first nonzero term of a given sequence to a verifier without revealing which term it is. Our protocol uses Θ (1) shuffles, which is asymptotically lower than that of an existing protocol of Fukusawa and Manabe which uses Θ (n) shuffles, where n is the length of the sequence. We also apply our protocol to construct zero-knowledge proof protocols for three well-known logic puzzles: ABC End View, Goishi Hiroi, and Toichika. These protocols enable a prover to physically show that he/she know solutions of the puzzles without revealing them. [ABSTRACT FROM AUTHOR]

An edge coloring of a graph G is to color all its edges such that adjacent edges receive different colors. It is acyclic if the subgraph induced by any two colors does not contain a cycle. Fiamcik (Math Slovaca 28:139-145, 1978) and Alon et al. (J Graph Theory 37:157-167, 2001) conjectured that every simple graph with maximum degree Δ is acyclically edge (Δ + 2) -colorable — the well-known acyclic edge coloring conjecture. Despite many major breakthroughs and minor improvements, the conjecture remains open even for planar graphs. In this paper, we prove that planar graphs are acyclically edge (Δ + 5) -colorable. Our proof has two main steps: Using discharging methods, we first show that every non-trivial planar graph contains a local structure in one of the eight characterized groups; we then deal with each local structure to color the edges in the graph acyclically using no more than Δ + 5 colors by an induction on the number of edges. [ABSTRACT FROM AUTHOR]