Coflow scheduling is a challenging optimization problem that underlies many data transmission and parallel computing applications. In this paper, we study the indivisible coflow scheduling problem on parallel identical machines with the objective to minimize the makespan, i.e., the completion time of the last flow. In our problem setting, the number of the input/output ports in each machine is a fixed

As global climate change intensifies, the agricultural sector, responsible for over 30% of global greenhouse gas emissions, faces an urgent imperative to mitigate emissions and align with international climate commitments. Carbon sink trading, a market-based mechanism that incentivizes emission reductions through sequestration credits, has emerged as an important tool for accelerating carbon peaking

The Internet of Things (IoT) application is an application and service that incorporates both the physical and information world. Similarly, it is difficult for existing health systems to provide privacy-aware aggregate authentication and fine-grained access control. To bridge the concern, a smart health system (SHS) with Deep Kronecker Network_key generation (DKN_keyGen) for privacy-aware aggregate

In this paper, we investigate the maximum weight k-cycle (k-path) partition problem (MaxWkCP/MaxWkPP for short). The input consists of an undirected complete graph \(G=(V,E)\) with \(|V|=kn\), where k, n are positive integers, and a non-negative weight function on E, the objective is to determine n vertex disjoint k-cycles (k-paths), which are cycles (paths) containing exactly k vertices, covering

In this ever-evolving world of threats, e-mail security is becoming one of the biggest concerns because attackers are constantly searching for new techniques to bypass the existing security measures. Emails containing phishing, malware and other security threats have become far more common place, which is why there is a need to implement new and more efficient adaptive threat detection frameworks.

For graphs G and H, the Ramsey number R(G, H) is the smallest r such that any red-blue edge coloring of \(K_r\) contains a red G or a blue H. The path-critical Ramsey number \(R_{\pi }(G,H)\) is the largest n such that any red-blue edge coloring of \(K_r \setminus P_{n}\) contains a red G or a blue H, where \(r=R(G,H)\) and \(P_{n}\) is a path of order n. In this note, we show a general upper bound

We study a class of binary fractional programs commonly encountered in important application domains such as assortment optimization and facility location. These problems are known to be NP-hard to approximate within any constant factor, and existing solution approaches typically rely on mixed-integer linear programming or second-order cone programming reformulations. These methods often utilize linearization

We study the robust maximum flow problem and the robust maximum flow over time problem where a given number of arcs \(\Gamma \) may fail or may be delayed. Two prominent models have been introduced for these problems: either one assigns flow to arcs fulfilling weak flow conservation in any scenario, or one assigns flow to paths where an arc failure or delay affects a whole path. We provide a unifying

Currently, many countries are on the process of reforming their health care payment systems from post-payment to pre-payment. To explore the impact of pre-payment schemes on health system performance we investigate the two payment schemes, bundled payment (BP) and total prepayment (TP), on performance in a medical cost-sharing system. Under the BP scheme, the government compensates hospitals with a

In this paper, we study the independent quadratic assignment problem which is a variation of the well-known Koopmans–Beckman quadratic assignment problem. The problem is strongly NP-hard and is also hard to approximate. Some polynomially solvable special cases are identified along with a complete characterization of linearizable instances of the problem, the validity of which is shown to be verifiable

We explore the problem of combinatorial contract design, a subject introduced and studied by Dütting et al. (2023). Previous research has focused on the challenge of selecting an unconstrained subset of agents, particularly when the principal’s utility function exhibits XOS or submodular characteristics related to the subset of agents that exert effort. Our study extends this existing line of research

In this paper, we consider the W-prize-collecting scheduling problem on a single machine with submodular rejection penalties. In this problem, we are given one machine, n jobs and a value W. Every job has a processing time and a profit. Each job is either accepted and processed on the machine, or rejected and a rejection penalty is paid. The objective is to minimize the sum of the makespan of the accepted

There are numerous combinatorial algorithms for classical min-cost flow problems and their simpler variants like max flow or shortest path problems. It is well-known that many of these algorithms are related to the Simplex method and the more general circuit augmentation schemes: prime examples are the network Simplex method, a refinement of the primal Simplex method, and min-mean cycle canceling,

We study mechanism design with predictions in the single (obnoxious) facility location games with candidate locations on the real line, which complements the existing literature on mechanism design with predictions. We first consider the single facility location games with candidate locations, where each agent prefers the facility (e.g., a school) to be located as close to her as possible. We study

For a real number \(\omega \), a weak game of threats (N, v) consists of a set N of n players and a function \(v:2^N\rightarrow \mathbb {R}\) such that \(\omega v(\emptyset )+(1-\omega )v(N)=0\), where \(v(\emptyset )\ne 0\) possibly. It is shown that there exists a unique value with respect to \(\omega \) for weak games of threats that satisfies efficiency, linearity, symmetry and the null player

In this paper, we consider the partition set cover problem with penalties. In this problem, we have a universe U, a partition \(\mathscr {P}=\{P_{1},\ldots ,P_{r}\}\) of U, and a collection \(\mathscr {S}=\{S_{1},\ldots ,S_{m}\}\) of nonempty subsets of U satisfying \(\bigcup _{S_i\in \mathscr {S}} S_i=U\). In addition, each \(P_t\) \((t\in [r])\) is associated with a covering requirement \(k_t\) as

Substar reliability defined as the probability that a fault-free substar of a certain scale is still available in the star network \(S_n\) when the occurrence of faults. The substar reliability is one of the most practical reliability measures because a user in the current star multiprocessors is given a certain substar for the execution of his/her program. Wu and Latifi(Inf. Sci. 178 (2008)) derived

L-shaped floorplans are defined by rectangular modules enclosed within a rectilinear outer boundary, forming an L-shape that can not be altered through simple extension or contraction of a boundary wall. The boundary of such floorplans comprises five convex corners and one concave corner. The concave corner on the boundary of the plan can not be converted into a convex corner without altering the horizontal

We study the SONET edge partition problem that models telecommunication network design to partition the edge set of a given graph into several edge-disjoint subgraphs, such that each subgraph has size no greater than a given capacity k and the sum of the orders of these subgraphs is minimized. The problem is NP-hard when \(k \ge 3\) and admits an \(O(\log k)\)-approximation algorithm. For small capacity

Diagnosis of thyroid disease is a most important cause in the field of medicinal research and it is a complex onset axiom. Secretion of Thyroid hormone plays a major role in the regulation of metabolism. Hence, it is very significant to predict thyroid disease in the initial stage, which is helpful for preventing more serious health complications due to thyroid cancer. The diagnostic accuracy of machine

In a graph G, the normal k-edge coloring \(\sigma \) is defined as the conventional edge coloring of G using the color set \(\left[ k \right] =\left\{ 1,2,\cdots ,k \right\} \). If the condition \(S\left( u \right) \ne S\left( v \right) \) holds for any edge \(uv\in E\left( G \right) \), where \(S\left( u \right) =\sum \nolimits _{uv\in E\left( G \right) }{\sigma \left( uv \right) }\), then \(\sigma

In recent years, k-submodular functions have garnered significant attention due to their natural extension of submodular functions and their practical applications, such as influence maximization and sensor placement. Influence maximization involves selecting a set of nodes in a network to maximize the spread of information, while sensor placement focuses on optimizing the locations of sensors to maximize

In the A-Multi3-Hitting Set problem (A-M3HS), where \(A \subseteq \{1,2,3\}\), the input is a hypergraph G in which the hyperedges have sizes at most 3 and an integer k, and the goal is to decide if there is a set S of at most k vertices such that \(|S \cap e| \in A\) for every hyperedge e. In this paper we give \(O^*(2.027^k)\)-time algorithms for \(\{1\}\)-M3HS and \(\{1,3\}\)-M3HS, and an \(O^*(1

Today, artificial bee colony (ABC) algorithm is one of the most popular swarm intelligence based optimization techniques. Although it was originally introduced to work on continuous space for numerical optimization problems, several researchers also successfully use the ABC for other problem types. In this study, variants of the ABC for scheduling problems are surveyed. Since the scheduling problems

Green manufacturing is used to describe an environmentally friendly manufacturing approach, which explicitly considers the impact of production on the environment and resources. Therefore, the production scheduling of solving energy conscious is in line with the focus of green manufacturing. In this paper, we consider the scheduling problems with rejection in the green manufacturing industry. The objective

In this paper, we focus on analyzing the 3-path vertex cover (3PVC) problem in a number of graph classes. Let \(G=(V,E)\) be a simple graph. A set \(C \subseteq V\) is called a k-path vertex cover of G, if each path of order k in G, contains at least one vertex from C. In the k-path vertex cover problem, we are given a graph G, and asked to find a k-path vertex cover of minimum size. For \(k=3\), the

This work considers a semi-online version of scheduling on m identical machines, where the objective is to minimize the makespan. In the variant studied here, jobs are presented sorted by non-increasing sizes, and a buffer of size k is available for storing at most k jobs. Every arriving job has to be either placed into the buffer until its assignment, or else it has to be assigned immediately to a

The cubic knapsack problem (CKP) is a combinatorial optimization problem, which can be seen both as a generalization of the quadratic knapsack problem (QKP) and of the linear Knapsack problem (KP). This problem consists of maximizing a cubic function of binary decision variables subject to one linear knapsack constraint. It has many applications in biology, project selection, capital budgeting problem

The cable-trench problem is defined as a linear combination of the shortest path and the minimum spanning tree problem. In particular, the goal is to find a spanning tree that simultaneously minimizes its total length and the total path length from a pre-defined root to all other vertices. Both, the minimum spanning tree and the shortest path problem are known to be efficiently solvable. However, a

Chaos optimization algorithm (COA) is an interesting alternative in a global optimization problem. Due to the non-repetition and ergodicity of chaos, it can explore the global search space at higher speeds than stochastic searches that depend on probabilities. To adjust the solution obtained by COA, guided local search algorithm (GLS) is integrated with COA to form a hybrid algorithm. GLS is a metaheuristic

Lifeline utility networks have been studied extensively within the domain of network reliability due to the prevalence of natural hazards. The reliability of these networks is typically investigated through graphs that retain their structural characteristics. This paper introduces novel connectivity-based reliability measures tailored for stochastic graphs with designated source vertices and failu

We study the two-center problem on cactus graphs in facility locations, which aims to place two facilities on the graph network to serve customers in order to minimize the maximum transportation cost. In our problem, the location of each customer is uncertain and may appear at O(m) points on the network with probabilities. More specifically, given are a cactus graph G and a set \(\mathcal {P}\) of

The product of a matrix chain consisting of n matrices can be computed in \(C_{n-1}\) (Catalan’s number) different ways, each identified by a distinct parenthesisation of the chain. The best algorithm to select a parenthesisation that minimises the cost runs in \(O(n \log n)\) time. Approximate algorithms run in O(n) time and find solutions that are guaranteed to be within a certain factor from optimal;

Fractional hedonic games are coalition formation games where a player’s utility is determined by the average value they assign to the members of their coalition. These games are a variation of graph hedonic games, which are a class of coalition formation games that can be succinctly represented. Due to their applicability in network clustering and their relationship to graph hedonic games, fractional

Analysis of higher-order organizations, represented as small connected subgraphs, is a fundamental task on complex networks. This paper studies a new problem of testing higher-order clusterability: given neighbor query access to an undirected graph, can we judge whether this graph can be partitioned into a few clusters of highly-connected cliques? This problem is an extension of the former work proposed

It’s a promising way to use Unmanned Aerial Vehicles (UAVs) as mobile base stations to collect data from sensor nodes, especially for large-scale wireless sensor networks. There are a lot of works that focus on improving the freshness of the collected data or the data collection efficiency by scheduling UAVs. Given that sensing data in certain applications is time-sensitive, with its value diminishing

In a hypergraph H(V, E), a subset of edges \(A\subseteq E\) forms an edge dominating set if each edge \(e\in E\setminus A\) is adjacent to at least one edge in A. The edge dominating number \(\gamma '(H)\) represents the smallest size of an edge dominating set in H. In this paper, we establish upper bounds on the edge dominating number for hypergraphs with minimum degree \(\delta \): (1) For \(\delta

In this paper, we consider the heterogeneous rooted tree cover (HRTC) problem, which further generalizes the rooted tree cover problem. Specifically, given a complete graph \(G=(V,E; w,f; r)\) and k construction teams, having nonuniform construction speeds \(\lambda _{1}\), \(\lambda _{2}\), \(\ldots \), \(\lambda _{k}\), where \(r\in V\) is a fixed common root, \(w:E\rightarrow {\mathbb {R}}^{+}\)

In this paper, we consider dynamic facility location problem with unit demand (DFLPUD). We propose a 1.52-approximation algorithm that skillfully integrates dual-fitting and greedy augmentation schemes. Our algorithmic framework begins by formulating DFLPUD as a set covering linear integer programming problem. Then we scale the opening cost of all facilities and use the solution of dual-fitting algorithm

Path cover is one of the well-known NP-hard problems that has received much attention. In this paper, we study a variant of path cover, denoted by \(\hbox {MPC}^{{4}+}_v\), to cover as many vertices in a given graph \(G = (V, E)\) as possible by a collection of vertex-disjoint paths each of order four or above. The problem admits an existing \(O(|V|^8)\)-time 2-approximation algorithm by applying several

High-performance computing extensively depends on parallel and distributed systems, necessitating the establishment of quantitative parameters to evaluate the fault tolerability of interconnection networks. The topological structures of interconnection networks in some parallel and distributed systems are designed as n-dimensional \((K_{9}-C_{9})^{n}\), obtained through the repeatedly application of

In real-life production, the cutting stock problem is often associated with additional constraints and objectives. Among the auxiliary objectives, two of the most relevant are the minimization of the number of different cutting patterns used and the minimization of the maximum number of simultaneously open stacks. The first auxiliary objective arises in manufacturing environments where the adjustment

We study the problem of how to fairly and efficiently allocate indivisible items (goods) to agents under budget constraints. Each item has a specific size, and each agent has a budget that limits the total size of the items received. To better explore efficiency, we introduce the concept of tightness, where all agents are tight. An agent is considered as tight if adding any unallocated item to her

This paper investigates the superposition problem of two or more individual semi-Markov decision processes (SMDPs). The new sequential decision process superposed by individual SMDPs is no longer an SMDP and cannot be handled by routine iterative algorithms, but we can expand its state spaces to obtain a hybrid-state SMDP. Using this hybrid-state SMDP as an auxiliary and inspired by the Robbins–Monro

Sustainable scheduling is getting more and more attention with economic globalization and sustainable manufacturing. However, fewer studies on the batch scheduling problem consider energy consumption. This paper conducts an investigation into the multi-objective hybrid flow shop batch-scheduling problem with the objectives of minimizing both the makespan and electrical energy consumption. The study

The Euclidean Steiner problem is the problem of finding a set \(\mathcal{S}\mathcal{t}\), with the shortest length, such that \(\mathcal{S}\mathcal{t}\cup \mathcal {A}\) is connected, where \(\mathcal {A}\) is a given set in a Euclidean space. The solutions \(\mathcal{S}\mathcal{t}\) to the Steiner problem will be called Steiner sets while the set \(\mathcal {A}\) will be called input. Since every

This paper studies the inefficiency of multiplicative approximate Nash Equilibrium for scheduling games. There is a set of machines and a set of jobs. Each job could choose one machine and be processed by the chosen one. A schedule is a \(\theta \)-NE if no player has the incentive to deviate so that it decreases its cost by a factor larger than \(1+\theta \). The \(\theta \)-NE is a generation of

In this paper, we investigate the data mule scheduling with handling time and time span constraints (DMSTC) in which the goal is to minimize the number of data mules dispatched from a depot that are used to serve target sensors located on a wireless sensor network. Each target sensor is associated with a handling time and each dispatched data mule must return to the original depot before time span

In the production scheduling of prefabricated components, a scheduling model considering the learning effect of processing time and the deterioration effect of delivery time in this paper is provided. More precisely, it asks for an assignment of a series of independent prefabricated jobs that arrived over time to a single machine for processing, and once the execution of a job is finished, it will

Let F(G) and \(F_t(G)\) be the zero forcing number and the total forcing number of a graph G, respectively. In this paper, we study the relationship between the total forcing number of a graph and its vertex covering number (or independence number), and prove that \(F_t(G) \le \Delta \alpha (G)\) and \(F_t(G) \le (\Delta - 1)\beta (G) + 1\) for any connected graph G with the maximum degree \(\Delta

Desktop cloud technology has revolutionized modern computing by enabling remote desktop functionality through cloud computing and virtualization. However, traditional fuzzy set theories struggle with the uncertainties inherent in these environments. This study addresses this gap by introducing the probabilistic p, q-rung orthopair fuzzy model, a novel extension that integrates probabilistic elements

Cloud computing has a powerful capability to handle a large number of tasks. However, this capability comes with significant energy requirements. It is critical to overcome the challenge of minimizing energy consumption within cloud service platforms without compromising service quality. In this paper, we propose a heuristic energy-saving scheduling algorithm, called Real-time Multi-workflow Energy-efficient

Consider a simple (edge weighted) graph \(G = \left( {V,E} \right)\) with \(\left| V \right| = n\) and \(\left| E \right| = m\). Let \(xy \in E\). The domination of a vertex \(z \in V\) by an edge \(xy\) is defined as \(z\) belonging to the closed neighborhood of either \(x\) or \(y\). An edge set \(W\) is considered as an edge-vertex dominating set of \(G\) if each vertex of \(V\) is dominated by

Determining the minimum genus of a graph is a fundamental optimisation problem in the study of network design and implementation as it gives a measure of non-planarity of graphs. In this paper, we are concerned with determining the smallest value of g such that a given graph G has an embedding on the orientable surface of genus g. In particular, we consider the Cartesian product of graphs since this

In this paper we study a scheduling problem with release dates and submodular rejection penalties on multiple (parallel) identical serial-batch machines. For this problem, each machine processes jobs in batches, jobs in a common batch start and finish simultaneously, and the duration of a batch is equal to the sum of a setup time and the total processing time of jobs in it. Some jobs are accepted and

Consider a set of items, X, with a total of n items, among which a subset, denoted as \(I\subseteq X\), consists of defective items. In the context of group testing, a test is conducted on a subset of items Q, where \(Q \subset X\). The result of this test is positive, yielding 1, if Q includes at least one defective item, that is if \(Q \cap I \ne \emptyset \). It is negative, yielding 0, if no defective

In this paper, a reduced quadratic surface support vector machine (RQSSVM) classification model is proposed and solved using the augmented Lagrange method. The new model can effectively handle nonlinearly separable data without kernel function selection and parameter tuning due to its quadratic surface segmentation facility. Meanwhile, the maximum margin term is replaced by an \(L_2\) regularization

In this paper, intuitionistic fuzzy multi-objective linear fractional programming problems (IFMOLFPs) with several fractional criteria, including profit/cost, profit/time, or profitability ratio maximization, are considered. Moreover, all parameters, with the exception of the decision variables, are characterized as triangular intuitionistic fuzzy numbers. The component-wise optimization method is

The performance of machine learning algorithms is significantly influenced by the quality of the underlying dataset, which often comprises a mix of essential and redundant features. Feature selection, which identifies and discards these redundant features, plays a pivotal role in reducing computational and storage overheads. Current methodologies for this task primarily span filter-based and wrapper-based

Solving the optimal order quantity for products with stock-dependent demand is a challenging task as both exact values of multiple parameters and complicated procedures are required. Motivated by this practical dilemma, this paper develops a new method to overcome the above-mentioned two challenges simultaneously. This new method, referred as two-stage AEOQ (adaptive economic order quantity) policy