This page has only limited features, please log in for full access.

Dr. José M. Sigarreta
Faculty of Mathematics. Autonomous University of Guerrero-Acapulco Campus, Calle Carlos E. Adame 54, Garita, CP-39650, Acapulco, Guerrero, Mexico

Basic Info


Research Keywords & Expertise

0 Discrete Mathematics
0 Geometry
0 topological indices
0 Alliances in graphs
0 Conformable and non-conformable calculus

Honors and Awards

The user has no records in this section


Career Timeline

The user has no records in this section.


Short Biography

The user biography is not available.
Following
Followers
Co Authors
The list of users this user is following is empty.
Following: 0 users

Feed

Journal article
Published: 29 July 2021 in Entropy
Reads 0
Downloads 0

We perform a detailed computational study of the recently introduced Sombor indices on random networks. Specifically, we apply Sombor indices on three models of random networks: Erdös-Rényi networks, random geometric graphs, and bipartite random networks. Within a statistical random matrix theory approach, we show that the average values of Sombor indices, normalized to the order of the network, scale with the average degree. Moreover, we discuss the application of average Sombor indices as complexity measures of random networks and, as a consequence, we show that selected normalized Sombor indices are highly correlated with the Shannon entropy of the eigenvectors of the adjacency matrix.

ACS Style

R. Aguilar-Sánchez; J. Méndez-Bermúdez; José Rodríguez; José Sigarreta. Normalized Sombor Indices as Complexity Measures of Random Networks. Entropy 2021, 23, 976 .

AMA Style

R. Aguilar-Sánchez, J. Méndez-Bermúdez, José Rodríguez, José Sigarreta. Normalized Sombor Indices as Complexity Measures of Random Networks. Entropy. 2021; 23 (8):976.

Chicago/Turabian Style

R. Aguilar-Sánchez; J. Méndez-Bermúdez; José Rodríguez; José Sigarreta. 2021. "Normalized Sombor Indices as Complexity Measures of Random Networks." Entropy 23, no. 8: 976.

Journal article
Published: 13 June 2021 in Applied Mathematics and Computation
Reads 0
Downloads 0

Let G be a graph with set of vertices V(G) and set of edges E(G). The Sombor index is a vertex-degree-based-topological index recently introduced by Ivan Gutman, defined asSO(G)=∑uv∈E(G)(du)2+(dv)2.In this paper we determine the extremal values of SO over trees with at most three branch vertices.

ACS Style

Roberto Cruz; Juan Rada; José M. Sigarreta. Sombor index of trees with at most three branch vertices. Applied Mathematics and Computation 2021, 409, 126414 .

AMA Style

Roberto Cruz, Juan Rada, José M. Sigarreta. Sombor index of trees with at most three branch vertices. Applied Mathematics and Computation. 2021; 409 ():126414.

Chicago/Turabian Style

Roberto Cruz; Juan Rada; José M. Sigarreta. 2021. "Sombor index of trees with at most three branch vertices." Applied Mathematics and Computation 409, no. : 126414.

Journal article
Published: 20 May 2021 in Mathematics
Reads 0
Downloads 0

In this work, we obtained new results relating the generalized atom-bond connectivity index with the general Randić index. Some of these inequalities for ABCα improved, when α=1/2, known results on the ABC index. Moreover, in order to obtain our results, we proved a kind of converse Hölder inequality, which is interesting on its own.

ACS Style

Paul Bosch; Edil Molina; José Rodríguez; José Sigarreta. Inequalities on the Generalized ABC Index. Mathematics 2021, 9, 1151 .

AMA Style

Paul Bosch, Edil Molina, José Rodríguez, José Sigarreta. Inequalities on the Generalized ABC Index. Mathematics. 2021; 9 (10):1151.

Chicago/Turabian Style

Paul Bosch; Edil Molina; José Rodríguez; José Sigarreta. 2021. "Inequalities on the Generalized ABC Index." Mathematics 9, no. 10: 1151.

Journal article
Published: 12 May 2021 in Symmetry
Reads 0
Downloads 0

Recently, the arithmetic–geometric index (AG) was introduced, inspired by the well-known and studied geometric–arithmetic index (GA). In this work, we obtain new bounds on the arithmetic–geometric index, improving upon some already known bounds. In particular, we show families of graphs where such bounds are attained.

ACS Style

Edil Molina; José Rodríguez; José Sánchez; José Sigarreta. Some Properties of the Arithmetic–Geometric Index. Symmetry 2021, 13, 857 .

AMA Style

Edil Molina, José Rodríguez, José Sánchez, José Sigarreta. Some Properties of the Arithmetic–Geometric Index. Symmetry. 2021; 13 (5):857.

Chicago/Turabian Style

Edil Molina; José Rodríguez; José Sánchez; José Sigarreta. 2021. "Some Properties of the Arithmetic–Geometric Index." Symmetry 13, no. 5: 857.

Journal article
Published: 06 May 2021 in Discrete Applied Mathematics
Reads 0
Downloads 0

The Sombor index SO, the reduced Sombor index SOred, and the average Sombor index SOavg have been introduced recently, and it was shown that they have good predictive potential in Mathematical Chemistry. We obtain in this work several new lower and upper bounds of these indices. Specifically, we find inequalities between SO and SOred and characterize the graphs where equality occurs. Also, we present inequalities for SO and SOred involving other topological indices, such as the first and second (variable) Zagreb indices and the forgotten index. Finally, we find bounds for SOavg.

ACS Style

Juan Rada; José M. Rodríguez; José M. Sigarreta. General properties on Sombor indices. Discrete Applied Mathematics 2021, 299, 87 -97.

AMA Style

Juan Rada, José M. Rodríguez, José M. Sigarreta. General properties on Sombor indices. Discrete Applied Mathematics. 2021; 299 ():87-97.

Chicago/Turabian Style

Juan Rada; José M. Rodríguez; José M. Sigarreta. 2021. "General properties on Sombor indices." Discrete Applied Mathematics 299, no. : 87-97.

Journal article
Published: 21 April 2021 in Sustainability
Reads 0
Downloads 0

In recent years, Multimetric Indices (MMIs) have received a lot of attention thanks to their ability to develop integrative evaluations of water quality, particularly in lagoons. In this article, we propose a new MMI for determining the water quality in lagoons. The proposed index is composed of biotic and abiotic indicators, in particular macroinvertebrates, macrophytes and morphological indicators. The proposed index is based on a geometric representation of a phenomenon associated with an ecological system, the ecosystem elements are mapped as vertices of a network and the relationship between them is represented by the corresponding edges. We classify the status of water bodies, from very low to very high using the ecological quality ratio. We compare our index with different different indices that measure water quality, such as General Biotic Index (JP(G)), Macrophyte Index for River (MIR) and Shannon diversity index (H’) and validate our index with Pearson’s correlation coefficient. A strong correlation with the JP(G) and MIR indices (R2 = 0.8605 and R2=0.7661, respectively) is obtained. Although the proposed index is composed of other indices, the independence of the proposed index with respect to its component indices is proven and the structure of the geometric model associated to the proposed network is studied. A close relationship between the measure called medium articulation and the geometric model associated with the proposed index is highlighted, which allows to determine the missing relationships in the network using structural analysis. The proposed index presents a more comprehensive measure than most indices currently used and has the advantage in the scalability, since other existing indicators can be integrated into our model.

ACS Style

Frank Hernández-Mira; José Rosas-Acevedo; Maximino Reyes-Umaña; Juan Violante-González; José Sigarreta-Almira; Nodari Vakhania. Multimetric Index to Evaluate Water Quality in Lagoons: A Biological and Geomorphological Approach. Sustainability 2021, 13, 4631 .

AMA Style

Frank Hernández-Mira, José Rosas-Acevedo, Maximino Reyes-Umaña, Juan Violante-González, José Sigarreta-Almira, Nodari Vakhania. Multimetric Index to Evaluate Water Quality in Lagoons: A Biological and Geomorphological Approach. Sustainability. 2021; 13 (9):4631.

Chicago/Turabian Style

Frank Hernández-Mira; José Rosas-Acevedo; Maximino Reyes-Umaña; Juan Violante-González; José Sigarreta-Almira; Nodari Vakhania. 2021. "Multimetric Index to Evaluate Water Quality in Lagoons: A Biological and Geomorphological Approach." Sustainability 13, no. 9: 4631.

Journal article
Published: 15 April 2021 in Symmetry
Reads 0
Downloads 0

The concept of arithmetic-geometric index was recently introduced in chemical graph theory, but it has proven to be useful from both a theoretical and practical point of view. The aim of this paper is to obtain new bounds of the arithmetic-geometric index and characterize the extremal graphs with respect to them. Several bounds are based on other indices, such as the second variable Zagreb index or the general atom-bond connectivity index), and some of them involve some parameters, such as the number of edges, the maximum degree, or the minimum degree of the graph. In most bounds, the graphs for which equality is attained are regular or biregular, or star graphs.

ACS Style

José Rodríguez; José Sánchez; José Sigarreta; Eva Tourís. Bounds on the Arithmetic-Geometric Index. Symmetry 2021, 13, 689 .

AMA Style

José Rodríguez, José Sánchez, José Sigarreta, Eva Tourís. Bounds on the Arithmetic-Geometric Index. Symmetry. 2021; 13 (4):689.

Chicago/Turabian Style

José Rodríguez; José Sánchez; José Sigarreta; Eva Tourís. 2021. "Bounds on the Arithmetic-Geometric Index." Symmetry 13, no. 4: 689.

Journal article
Published: 13 April 2021 in Symmetry
Reads 0
Downloads 0

In this paper we introduce a generalized Laplace transform in order to work with a very general fractional derivative, and we obtain the properties of this new transform. We also include the corresponding convolution and inverse formula. In particular, the definition of convolution for this generalized Laplace transform improves previous results. Additionally, we deal with the generalized harmonic oscillator equation, showing that this transform and its properties allow one to solve fractional differential equations.

ACS Style

Paul Bosch; Héctor Carmenate García; José Rodríguez; José Sigarreta. On the Generalized Laplace Transform. Symmetry 2021, 13, 669 .

AMA Style

Paul Bosch, Héctor Carmenate García, José Rodríguez, José Sigarreta. On the Generalized Laplace Transform. Symmetry. 2021; 13 (4):669.

Chicago/Turabian Style

Paul Bosch; Héctor Carmenate García; José Rodríguez; José Sigarreta. 2021. "On the Generalized Laplace Transform." Symmetry 13, no. 4: 669.

Journal article
Published: 16 March 2021 in Mathematics
Reads 0
Downloads 0

We consider the problem of scheduling n jobs with identical processing times and given release as well as delivery times on m uniform machines. The goal is to minimize the makespan, i.e., the maximum full completion time of any job. This problem is well-known to have an open complexity status even if the number of jobs is fixed. We present a polynomial-time algorithm for the problem which is based on the earlier introduced algorithmic framework blesscmore (“branch less and cut more”). We extend the analysis of the so-called behavior alternatives developed earlier for the version of the problem with identical parallel machines and show how the earlier used technique for identical machines can be extended to the uniform machine environment if a special condition on the job parameters is imposed. The time complexity of the proposed algorithm is O(γm2nlogn), where γ can be either n or the maximum job delivery time qmax. This complexity can even be reduced further by using a smaller number κ<n in the estimation describing the number of jobs of particular types. However, this number κ becomes only known when the algorithm has terminated.

ACS Style

Nodari Vakhania; Frank Werner. Branch Less, Cut More and Schedule Jobs with Release and Delivery Times on Uniform Machines. Mathematics 2021, 9, 633 .

AMA Style

Nodari Vakhania, Frank Werner. Branch Less, Cut More and Schedule Jobs with Release and Delivery Times on Uniform Machines. Mathematics. 2021; 9 (6):633.

Chicago/Turabian Style

Nodari Vakhania; Frank Werner. 2021. "Branch Less, Cut More and Schedule Jobs with Release and Delivery Times on Uniform Machines." Mathematics 9, no. 6: 633.

Original paper
Published: 13 March 2021 in Journal of Mathematical Chemistry
Reads 0
Downloads 0
ACS Style

R. Aguilar-Sánchez; J. A. Méndez-Bermúdez; José M. Rodríguez; José M. Sigarreta. Analytical and statistical studies of Rodriguez–Velazquez indices. Journal of Mathematical Chemistry 2021, 59, 1246 -1259.

AMA Style

R. Aguilar-Sánchez, J. A. Méndez-Bermúdez, José M. Rodríguez, José M. Sigarreta. Analytical and statistical studies of Rodriguez–Velazquez indices. Journal of Mathematical Chemistry. 2021; 59 (5):1246-1259.

Chicago/Turabian Style

R. Aguilar-Sánchez; J. A. Méndez-Bermúdez; José M. Rodríguez; José M. Sigarreta. 2021. "Analytical and statistical studies of Rodriguez–Velazquez indices." Journal of Mathematical Chemistry 59, no. 5: 1246-1259.

Journal article
Published: 26 February 2021 in Mathematics
Reads 0
Downloads 0

A nonempty subset DV of vertices of a graph G=(V,E) is a dominating set if every vertex of this graph is adjacent to at least one vertex from this set except the vertices which belong to this set itself. DV is a total k-dominating set if there are at least k vertices in set D adjacent to every vertex vV, and it is a global total k-dominating set if D is a total k-dominating set of both G and G¯. The global total k-domination number of G, denoted by γktg(G), is the minimum cardinality of a global total k-dominating set of G, GTkD-set. Here we derive upper and lower bounds of γktg(G), and develop a method that generates a GTkD-set from a GT(k1)D-set for the successively increasing values of k. Based on this method, we establish a relationship between γ(k1)tg(G) and γktg(G), which, in turn, provides another upper bound on γktg(G).

ACS Style

Frank Hernández Mira; Ernesto Parra Inza; José Sigarreta Almira; Nodari Vakhania. Properties of the Global Total k-Domination Number. Mathematics 2021, 9, 480 .

AMA Style

Frank Hernández Mira, Ernesto Parra Inza, José Sigarreta Almira, Nodari Vakhania. Properties of the Global Total k-Domination Number. Mathematics. 2021; 9 (5):480.

Chicago/Turabian Style

Frank Hernández Mira; Ernesto Parra Inza; José Sigarreta Almira; Nodari Vakhania. 2021. "Properties of the Global Total k-Domination Number." Mathematics 9, no. 5: 480.

Journal article
Published: 26 January 2021 in Mathematics
Reads 0
Downloads 0

Let G=(V,E) be a graph; a set D⊆V is a total dominating set if every vertex v∈V has, at least, one neighbor in D. The total domination number γt(G) is the minimum cardinality among all total dominating sets. Given an arbitrary graph G, we consider some operators on this graph; S(G),R(G), and Q(G), and we give bounds or the exact value of the total domination number of these new graphs using some parameters in the original graph G.

ACS Style

José M. Sigarreta. Total Domination on Some Graph Operators. Mathematics 2021, 9, 241 .

AMA Style

José M. Sigarreta. Total Domination on Some Graph Operators. Mathematics. 2021; 9 (3):241.

Chicago/Turabian Style

José M. Sigarreta. 2021. "Total Domination on Some Graph Operators." Mathematics 9, no. 3: 241.

Preprint
Published: 08 January 2021
Reads 0
Downloads 0

The problem of sequencing $n$ equal-length non-simultaneously released jobs with delivery times on $m$ uniform machines to minimize the maximum job completion time is considered. To the best of our knowledge, the complexity status of this classical scheduling problem remained open up to the date. We establish its complexity status positively by showing that it can be solved in polynomial time. We adopt for the uniform machine environment the general algorithmic framework of the analysis of behavior alternatives developed earlier for the identical machine environment. The proposed algorithm has the time complexity $O(\gamma m^2 n\log n)$, where $\gamma$ can be any of the magnitudes $n$ or $q_{\max}$, the maximum job delivery time. In fact, $n$ can be replaced by a smaller magnitude $\kappa

ACS Style

Nodari Vakhania; Frank Werner. A Polynomial Algorithm for Sequencing Jobs with Release and Delivery Times on Uniform Machines. 2021, 1 .

AMA Style

Nodari Vakhania, Frank Werner. A Polynomial Algorithm for Sequencing Jobs with Release and Delivery Times on Uniform Machines. . 2021; ():1.

Chicago/Turabian Style

Nodari Vakhania; Frank Werner. 2021. "A Polynomial Algorithm for Sequencing Jobs with Release and Delivery Times on Uniform Machines." , no. : 1.

Journal article
Published: 30 December 2020 in Symmetry
Reads 0
Downloads 0

A topic of current interest in the study of topological indices is to find relations between some index and one or several relevant parameters and/or other indices. In this paper we study two general topological indices Aα and Bα, defined for each graph H=(V(H),E(H)) by Aα(H)=∑ij∈E(H)f(di,dj)α and Bα(H)=∑i∈V(H)h(di)α, where di denotes the degree of the vertex i and α is any real number. Many important topological indices can be obtained from Aα and Bα by choosing appropriate symmetric functions and values of α. This new framework provides new tools that allow to obtain in a unified way inequalities involving many different topological indices. In particular, we obtain new optimal bounds on the variable Zagreb indices, the variable sum-connectivity index, the variable geometric-arithmetic index and the variable inverse sum indeg index. Thus, our approach provides both new tools for the study of topological indices and new bounds for a large class of topological indices. We obtain several optimal bounds of Aα (respectively, Bα) involving Aβ (respectively, Bβ). Moreover, we provide several bounds of the variable geometric-arithmetic index in terms of the variable inverse sum indeg index, and two bounds of the variable inverse sum indeg index in terms of the variable second Zagreb and the variable sum-connectivity indices.

ACS Style

José M. Sigarreta. Mathematical Properties of Variable Topological Indices. Symmetry 2020, 13, 43 .

AMA Style

José M. Sigarreta. Mathematical Properties of Variable Topological Indices. Symmetry. 2020; 13 (1):43.

Chicago/Turabian Style

José M. Sigarreta. 2020. "Mathematical Properties of Variable Topological Indices." Symmetry 13, no. 1: 43.

Article
Published: 30 December 2020 in Acta Mathematica Sinica, English Series
Reads 0
Downloads 0

The paper provides integral representations for solutions to a certain first order partial differential equation natural arising in the factorization of the Lamé—Navier system with the help of Clifford analysis techniques. These representations look like in spirit to the Borel—Pompeiu and Cauchy integral formulas both in three and higher dimensional setting.

ACS Style

Ricardo Abreu-Blaya; Juan Bory-Reyes; Marcos Antonio Herrera-Peláez; José María Sigarreta-Almira. Integral Representation Formulas Related to the Lamé—Navier System. Acta Mathematica Sinica, English Series 2020, 36, 1341 -1356.

AMA Style

Ricardo Abreu-Blaya, Juan Bory-Reyes, Marcos Antonio Herrera-Peláez, José María Sigarreta-Almira. Integral Representation Formulas Related to the Lamé—Navier System. Acta Mathematica Sinica, English Series. 2020; 36 (12):1341-1356.

Chicago/Turabian Style

Ricardo Abreu-Blaya; Juan Bory-Reyes; Marcos Antonio Herrera-Peláez; José María Sigarreta-Almira. 2020. "Integral Representation Formulas Related to the Lamé—Navier System." Acta Mathematica Sinica, English Series 36, no. 12: 1341-1356.

Book chapter
Published: 26 November 2020 in Multicriteria Optimization - Pareto-Optimality and Threshold-Optimality
Reads 0
Downloads 0

Multi-objective optimization problems are important as they arise in many practical circumstances. In such problems, there is no general notion of optimality, as there are different objective criteria which can be contradictory. In practice, often there is no unique optimality criterion for measuring the solution quality. The latter is rather determined by the value of the solution for each objective criterion. In fact, a practitioner seeks for a solution that has an acceptable value of each of the objective functions and, in practice, there may be different tolerances to the quality of the delivered solution for different objective functions: for some objective criteria, solutions that are far away from an optimal one can be acceptable. Traditional Pareto-optimality approach aims to create all non-dominated feasible solutions in respect to all the optimality criteria. This often requires an inadmissible time. Besides, it is not evident how to choose an appropriate solution from the Pareto-optimal set of feasible solutions, which can be very large. Here we propose a new approach and call it multi-threshold optimization setting that takes into account different requirements for different objective criteria and so is more flexible and can often be solved in a more efficient way.

ACS Style

Nodari Vakhania; Frank Werner. A Brief Look at Multi-Criteria Problems: Multi-Threshold Optimization versus Pareto-Optimization. Multicriteria Optimization - Pareto-Optimality and Threshold-Optimality 2020, 1 .

AMA Style

Nodari Vakhania, Frank Werner. A Brief Look at Multi-Criteria Problems: Multi-Threshold Optimization versus Pareto-Optimization. Multicriteria Optimization - Pareto-Optimality and Threshold-Optimality. 2020; ():1.

Chicago/Turabian Style

Nodari Vakhania; Frank Werner. 2020. "A Brief Look at Multi-Criteria Problems: Multi-Threshold Optimization versus Pareto-Optimization." Multicriteria Optimization - Pareto-Optimality and Threshold-Optimality , no. : 1.

Journal article
Published: 02 November 2020 in Mathematics
Reads 0
Downloads 0

A basic supply chain scheduling problem in which the orders released over time are to be delivered into the batches with unlimited capacity is considered. The delivery of each batch has a fixed cost D, whereas any order delivered after its release time yields an additional delay cost equal to the waiting time of that order in the system. The objective is to minimize the total delivery cost of the batches plus the total delay cost of the orders. A new algorithmic framework is proposed based on which fast algorithms for the solution of this problem are built. The framework can be extended to more general supply chain scheduling models and is based on a theoretical study of some useful properties of the offline version of the problem. An online scenario is considered as well, when at each assignment (order release) time the information on the next order released within the following T time units is known but no information on the orders that might be released after that time is known. For the online setting, it is shown that there is no benefit in waiting for more than D time units for incoming orders, i.e., potentially beneficial values for T are 0

ACS Style

Nodari Vakhania; Badri Mamporia. Fast Algorithms for Basic Supply Chain Scheduling Problems. Mathematics 2020, 8, 1919 .

AMA Style

Nodari Vakhania, Badri Mamporia. Fast Algorithms for Basic Supply Chain Scheduling Problems. Mathematics. 2020; 8 (11):1919.

Chicago/Turabian Style

Nodari Vakhania; Badri Mamporia. 2020. "Fast Algorithms for Basic Supply Chain Scheduling Problems." Mathematics 8, no. 11: 1919.

Original paper
Published: 25 September 2020 in Journal of Mathematical Chemistry
Reads 0
Downloads 0

The concept of general sum connectivity index was introduced in the area of chemical graph theory recently. Several of its particular cases have proven to correlate well with physical and chemical properties of some molecules. The main aim of this paper is to obtain new inequalities relating the general sum connectivity indices of a graph and its line graph.

ACS Style

Walter Carballosa; Domingo Pestana; José M. Sigarreta; Eva Tourís. Relations between the general sum connectivity index and the line graph. Journal of Mathematical Chemistry 2020, 58, 2273 -2290.

AMA Style

Walter Carballosa, Domingo Pestana, José M. Sigarreta, Eva Tourís. Relations between the general sum connectivity index and the line graph. Journal of Mathematical Chemistry. 2020; 58 (10):2273-2290.

Chicago/Turabian Style

Walter Carballosa; Domingo Pestana; José M. Sigarreta; Eva Tourís. 2020. "Relations between the general sum connectivity index and the line graph." Journal of Mathematical Chemistry 58, no. 10: 2273-2290.

Journal article
Published: 15 September 2020 in Chaos: An Interdisciplinary Journal of Nonlinear Science
Reads 0
Downloads 0

In this article, new information dimensions of complex networks are introduced underpinned by fractional order entropies proposed in the literature. This fractional approach of the concept of information dimension is applied to several real and synthetic complex networks, and the achieved results are analyzed and compared with the corresponding ones obtained using classic information dimension based on the Shannon entropy. In addition, we have investigated an extensive classification of the treated complex networks in correspondence with the fractional information dimensions.

ACS Style

Aldo Ramirez-Arellano; José María Sigarreta Almira; Juan Bory-Reyes. Fractional information dimensions of complex networks. Chaos: An Interdisciplinary Journal of Nonlinear Science 2020, 30, 093125 .

AMA Style

Aldo Ramirez-Arellano, José María Sigarreta Almira, Juan Bory-Reyes. Fractional information dimensions of complex networks. Chaos: An Interdisciplinary Journal of Nonlinear Science. 2020; 30 (9):093125.

Chicago/Turabian Style

Aldo Ramirez-Arellano; José María Sigarreta Almira; Juan Bory-Reyes. 2020. "Fractional information dimensions of complex networks." Chaos: An Interdisciplinary Journal of Nonlinear Science 30, no. 9: 093125.

Journal article
Published: 07 September 2020 in Mathematics
Reads 0
Downloads 0

We propose an approximation algorithm for scheduling jobs with release and delivery times on a single machine with the objective to minimize the makespan. The algorithm is based on an implicit enumeration of the set of complete solutions in a search tree. By analyzing specific structural properties of the solutions created in each branch of the solution tree, a certain approximation factor of each solution from that branch is calculated. Our algorithm guarantees approximation factor 1+1/κ for a generated solution if there are κ jobs with a specified property in that solution (typically, the longer the length of the path from the root to the node representing that solution in the solution tree, the larger the κ value). We have carried out an extensive computational study to verify the practical performance of our algorithm and the effectiveness of the approximation factor provided by us. While our problem instances are generated randomly, we have discarded a considerable number of the instances, ones which were already solved optimally by the earlier known dominance rules. For the vast majority of the tested problem instances, within a short running time of our algorithm parameter κ becomes sufficiently large so that the approximation factor which the algorithm guarantees becomes better than that provided by the earlier known approximation algorithms.

ACS Style

Federico Alonso-Pecina; José Hernández; José Maria Sigarreta; Nodari Vakhania. Fast Approximation for Scheduling One Machine. Mathematics 2020, 8, 1524 .

AMA Style

Federico Alonso-Pecina, José Hernández, José Maria Sigarreta, Nodari Vakhania. Fast Approximation for Scheduling One Machine. Mathematics. 2020; 8 (9):1524.

Chicago/Turabian Style

Federico Alonso-Pecina; José Hernández; José Maria Sigarreta; Nodari Vakhania. 2020. "Fast Approximation for Scheduling One Machine." Mathematics 8, no. 9: 1524.