-
Article
Moderate exponential-time algorithms for scheduling problems
This survey investigates the field of moderate exponential-time algorithms for \(\mathcal NP\) ...
-
Article
On fairness and diversification in WTA and ATP tennis tournaments generation
Single-elimination (knockout) tournaments are the standard paradigm for both main tennis professional associations, WTA and ATP. Schedules are generated by allocating first seeded and then unseeded players wit...
-
Article
Minimizing total completion time in the two-machine no-idle no-wait flow shop problem
We consider the two-machine total completion time flow shop problem with additional requirements. These requirements are the so-called no-idle constraint where the machines must operate with no inserted idle t...
-
Article
An exact approach for the bilevel knapsack problem with interdiction constraints and extensions
We consider the bilevel knapsack problem with interdiction constraints, an extension of the classic 0–1 knapsack problem formulated as a Stackelberg game with two agents, a leader and a follower, that choose i...
-
Article
Exponential time algorithms for just-in-time scheduling problems with common due date and symmetric weights
This paper focuses on the solution, by exact exponential-time algorithms, of just-in-time scheduling problems when jobs have symmetric earliness/tardiness weights and share a non restrictive common due date. F...
-
Article
The Longest Processing Time rule for identical parallel machines revisited
We consider the \(P_m || C_{\max }\)Pm||Cmax scheduling problem where the goal is to schedule n jobs on m identical parallel machines \((m < n)\)(m<n) to minimize makespan. We revisit the famous Longest Processin...
-
Article
A tight linear time \(\frac{13}{12}\) -approximation algorithm for the \(P2 || C_{\max }\) problem
We consider problem \(P2 || C_{\max }\) ...
-
Chapter and Conference Paper
Lower Bounds and a New Exact Approach for the Bilevel Knapsack with Interdiction Constraints
We consider the Bilevel Knapsack with Interdiction Constraints, an extension of the classic 0-1 knapsack problem formulated as a Stackelberg game with two agents, a leader and a follower, that choose items fro...
-
Chapter and Conference Paper
Approximation Results for the Incremental Knapsack Problem
We consider the 0–1 Incremental Knapsack Problem where the knapsack capacity grows over time periods and if an item is placed in the knapsack in a certain period, it cannot be removed afterwards. The problem c...
-
Article
Minimizing the number of tardy jobs in two-machine settings with common due date
We consider two-machine scheduling problems with job selection. We analyze first the two-machine open shop problem and provide a best possible linear time algorithm. Then, a best possible linear time algorithm...
-
Article
An exact semidefinite programming approach for the max-mean dispersion problem
This paper proposes an exact algorithm for the Max-Mean dispersion problem ( \(Max-Mean DP\) ...
-
Article
MP or not MP: that is the question
It is well known that in the twentieth century, mathematical programming (MP) modeling and particularly linear programming (LP) modeling, even though strongly applied to combinatorial optimization, were not to...
-
Article
Efficient algorithms for the max \(k\) -vertex cover problem
Given a graph \(G(V,E)\) of order \(n\)
-
Article
A variable neighborhood search based matheuristic for nurse rostering problems
A practical nurse rostering problem, which arises at a ward of an Italian private hospital, is considered. In this problem, it is required each month to assign shifts to the nursing staff subject to various re...
-
Article
A matheuristic approach for the two-machine total completion time flow shop problem
This paper deals with the two-machine total completion time flow shop problem. We present a so-called matheuristic post processing procedure that improves the objective function value with respect to the solution...
-
Chapter and Conference Paper
A Hybrid Heuristic Approach Based on a Quadratic Knapsack Formulation for the Max-Mean Dispersion Problem
The paper deals with the Max-Mean Dispersion Problem ( \(Max-Mean DP\) ) belonging to the general category of clustering problems...
-
Chapter and Conference Paper
On the max min vertex cover Problem
We address the max min vertex cover problem, which is the maximization version of the well studied min independent dominating set problem, known to be NP-hard and highly inapproximable in polynomial time. We pres...
-
Chapter and Conference Paper
A Constraint Generation Approach for the Two-Machine Flow Shop Problem with Jobs Selection
We consider a job selection problem in a two-stage flow shop. The objective is to select the best job subset with a given cardinality to minimize the makespan. This problem is known to be ordinary ...
-
Article
Improving an exact approach for solving separable integer quadratic knapsack problems
We consider the specially structured (pure) integer Quadratic Multi-Knapsack Problem (QMKP) tackled in the paper “Exact solution methods to solve large scale integer quadratic knapsack problems” by D. Quadri, E. ...
-
Chapter and Conference Paper
Efficient Algorithms for the max k -vertex cover Problem
We first devise moderately exponential exact algorithms for max k -vertex cover, with time-complexity exponential in n but with polynomial space-complexity by develo** a branch and ...