Croatian Operational Research Review

A fresh look at a randomized massively parallel graph coloring algorithm

Boštjan Gabrovšek, Janez Žerovnik — Mon, 07 Oct 2024 00:00:00 +0200

Petford and Welsh introduced a sequential heuristic algorithm to provide an approximate solution to the NP-hard graph coloring problem. The algorithm is based on the antivoter model and mimics the behavior of a physical process based on a multi-particle system of statistical mechanics. It was later shown that the algorithm can be implemented in a massively parallel model of computation. The increase in computational processing power in recent years allows us to perform an extensive analysis of the algorithms on a larger scale, leading to the possibility of a more comprehensive understanding of the behavior of the algorithm, including the phase transition phenomena.

On some quantitative indicators of a few features of electoral systems

Tomislav Marošević, Josip Miletić — Mon, 07 Oct 2024 00:00:00 +0200

Electoral systems can be analyzed by means of their numerous properties. Some quantitative indicators of a few technical features of electoral systems are considered. With respect to the effective number of parties in a electoral system, one can observe some known indicators (e.g., fractionalization of vote shares, the Laakso-Taagepera index, the Wildgen index, the Molinar index). With regard to the government stability, one can look at the indicator which is called the expectation of government stability. These indicators are examined from the empirical point of view, i.e., in relation of elections in different countries.

CB-SEM vs PLS-SEM comparison in estimating the predictors of investment intention

Marija Vuković — Mon, 07 Oct 2024 00:00:00 +0200

This paper compares different structural equation modeling approaches in estimating the predictors of investment intention. Covariance-based structural equation modeling (CB-SEM) and partial least squares structural equation modeling (PLS-SEM) techniques were compared in the estimation of the model according to the theory of planned behavior (TPB). Additionally, the consistent PLS algorithm (PLSc) was taken into consideration in the methods comparison. To determine which factors affect stock investment intention, a TPB model with attitude towards behavior, perceived behavioral control, and subjective norm as independent variables was estimated using three different approaches. The factors in the model were measured using survey indicators and the final sample included 200 Croatian residents. The results mostly show matching conclusions about the investment intention predictors, with a small difference observed in the PLS-SEM method. It can also be concluded that the factor loadings are higher according to PLS-SEM, as well as the indicators of convergent validity and reliability. On the other hand, CB-SEM shows stronger structural paths than PLS-SEM, and PLSc results are closer to those of CB-SEM. While CB-SEM shows better model fit, PLS-SEM shows high predictive power. This research further provides explanations of the differences and guidelines on when to use which approach.

A cost analysis of single-server discouraged arrivals with differentiated vacation queueing model

Srinivasan Keerthana, Jaisingh Ebenesar Anna Bagyam, Ramachandran Remya — Mon, 07 Oct 2024 00:00:00 +0200

This paper investigates an M/M/1 queueing system with differentiated vacations and discouraged arrivals, focusing on two types of vacations. The server switches to type I vacation with rate γ1 when the system is empty during an active state. If no customers are waiting when it returns from a type I vacation, it then switches to a type II vacation with a rate of γ2. Both vacation times and service duration follow exponential distributions. The study utilises the Probability Generating Function (PGF) technique to derive steady-state solutions for both vacation policies. Furthermore, the research explores relevant performance metrics and provides numerical examples to illustrate the system's behaviour under various conditions. The cost analysis of the M/M/1 differentiated vacation system with discouraged arrival queueing and various aspects of the system's behaviour under different arrival rates (λ, λ1, λ2) are discussed

ANFIS computing and cost optimization of an M/M/c/M queue with feedback and balking customers under a hybrid hiatus policy

Aimen Dehimi, Mohamed Boualem, Sami Kahla, Louiza Berdjoudj — Mon, 07 Oct 2024 00:00:00 +0200

The present investigation studies a hybrid hiatus policy for a finite-space Markovian queue, incorporating realistic features such as Bernoulli feedback, multiple servers, and balking customers. A hybrid hiatus policy combines both a working hiatus and a complete hiatus. As soon as the system becomes empty, the servers switch to a working hiatus. During a working hiatus, the servers operate at a reduced service rate. Upon completion of the working hiatus and in the absence of waiting customers, the servers enter a complete hiatus. Once the complete hiatus period concludes, the servers resume normal operations and begin serving waiting customers. In the context of Bernoulli feedback, the dissatisfied customer can re-enter the system to receive another service. By utilizing the Markov recursive approach, we examined the steady-state probabilities of the system and queue sizes and other queueing indices, viz. Average queue length, average waiting time, throughput, etc. Using the Quasi-Newton method, a cost function is developed to determine the optimal values of the system’s decision variables. Furthermore, a soft computing approach based on an adaptive neuro-fuzzy inference system (ANFIS) is employed to validate the accuracy of the obtained results.

Multi server queuing model with dynamic power shifting and performance efficiency factor

Sreelatha V, Elliriki Mamatha, Chandra S Reddy, Krishna Anand S — Mon, 07 Oct 2024 00:00:00 +0200

The need for high performance models in the queuing systems; availability in the fields of computing and communication systems and logistics management poses extensive challenges in design and development of the appropriate modeling. In this work, we propose a robust probabilistic model to mitigate these problems by appropriately choosing a multi-server queuing system with dynamic service facility. The arrival substances, such as packets or jobs or customers or consumers, follow a Poisson arrival process and these arrivals enter a queuing system according to FIFO discipline. The system designed in the system is armed with a fixed number of service stations, in which some servers are capable of allocating additional service capacity by adjusting dynamically. When a customer arrives at the system, if a free server is available, it is immediately served by one of the free processors; if no server is free, that is all are busy, the arrived job is accommodated in the queue and waits for service in the system. In this paper, we proposed a stochastic model to handle peak loads efficiently, boosting service capacity during burst arrivals. Numerical results presented in this paper are generated by the spectral expansion method to demonstrate the model’s performance, offering insights into its efficiency and accuracy. Furthermore, we derived some important special cases of speedup factor, which provide the mathematical estimation of system performance in terms of computation and communication times.

A hybrid population-based algorithm for solving the Minimum Dominating Set Problem

Belkacem Zouilekh, Sadek Bouroubi — Mon, 07 Oct 2024 00:00:00 +0200

The Minimum Dominating Sets (MDS) problem is pivotal across diverse fields like social networks and ad hoc wireless networks, representing a significant NP-complete challenge in graph theory. To tackle this, we propose a novel hybrid cuckoo search approach. While cuckoo search is renowned for its wide search space exploration, we enhance it with intensification methods and genetic crossover operators for improved performance. Comprehensive experimental evaluations against state-of-the-art techniques validate our approach's effectiveness.

Exact methods for the longest induced cycle problem

Ahmad Turki Anaqreh, Boglarka G.-Toth, Tamas Vinko — Mon, 07 Oct 2024 00:00:00 +0200

The longest induced (or chordless) cycle problem is a graph problem classified as NP-complete and involves the task of determining the largest possible subset of vertices within a graph in such a way that the induced subgraph forms a cycle. Within this paper, we present three integer linear programs specifically formulated to yield optimal solutions for this problem. The branch-and-cut algorithm has been used for two models that cannot be directly solved by any MILP solver. To demonstrate the computational efficiency of these methods, we utilize them on a range of real-world graphs as well as random graphs. Additionally, we conduct a comparative analysis against approaches previously proposed in the literature.