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

Let S={x1,…,xn} be a gcd-closed set (i.e. (xi,xj)∈S for all 1≤i,j≤n). In 2002, Hong proposed the divisibility problem of characterizing all gcd-closed sets S with |S|≥4 such that the GCD matrix (S) divides the LCM matrix [S] in the ring Mn(Z). For x∈S, let GS(x):={z∈S:z

A multidimensional nonnegative matrix is called polystochastic if the sum of its entries over each line is equal to 1. The permanent of a multidimensional matrix is the sum of products of entries over all diagonals. We prove that if d is even, then the permanent of a d-dimensional polystochastic matrix of order 4 is positive, and for odd d, we give a complete characterization of d-dimensional polystochastic

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 prove that there exists a constant C so that, for all s,k∈N, if G has average degree at least kCs3 and does not contain Ks,s as a subgraph then it contains an induced subgraph which is C4-free and has average degree at least k. It was known that some function of s and k suffices, but this is the first explicit bound. We give several applications of this result, including short and streamlined proofs

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

We prove a conjecture of Kim and Oum that every proper pivot-minor-closed class of graphs has the strong Erdős-Hajnal property. More precisely, for every graph H, there exists ϵ>0 such that every n-vertex graph with no pivot-minor isomorphic to H contains two sets A,B of vertices such that |A|,|B|⩾ϵn and A is complete or anticomplete to B.

For a finite (not necessarily abelian) group (Γ,⋅), let n(Γ) denote the smallest positive integer n such that for each labelling of the arcs of the complete digraph of order n using elements from Γ, there exists a directed cycle such that the arc-labels along the cycle multiply to the identity. Alon and Krivelevich [2] initiated the study of the parameter n(⋅) on cyclic groups and proved n(Zq)=O(qlog⁡q)

Let R be a group and let S be a subset of R. The Haar graph Haar(R,S) of R with connection set S is the graph having vertex set R×{−1,1}, where two distinct vertices (x,−1) and (y,1) are declared to be adjacent if and only if yx−1∈S. The name Haar graph was coined by Tomaž Pisanski in one of the first investigations on this class of graphs.

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