On the <Emphasis Type="Italic">m</Emphasis>-clique free interval subgraphs polytope: polyhedral analysis and applications

In this paper we study the m-clique free interval subgraphs. We investigate the facial structure of the polytope defined as the convex hull of the incidence vectors associated with these subgraphs. We also present some facet-defining inequalities to strengthen the associated linear relaxation. As an application, the generalized open-shop problem with disjunctive constraints (GOSDC) is considered. Indeed, by a projection on a set of variables, the m-clique free interval subgraphs represent the solution of an integer linear program solving the GOSDC presented in this paper. Moreover, we propose exact and heuristic separation algorithms, which are exploited into a Branch-and-cut algorithm for solving the GOSDC. Finally, we present and discuss some computational results.     

Approximation algorithms for the makespan minimization with positive tails on a single machine with a fixed non-availability interval

In this article, we consider the non-resumable case of the single machine scheduling problem with a fixed non-availability interval. We aim to minimize the makespan when every job has a positive tail. We propose a polynomial approximation algorithm with a worst-case performance ratio of 3/2 for this problem. We show that this bound is tight. We present a dynamic programming algorithm and we show that the problem has an FPTAS (Fully Polynomial Time Approximation Algorithm) by exploiting the well-known approach of Ibarra and Kim (J. ACM 22:463–468, 1975). Such an FPTAS is strongly polynomial. The obtained results outperform the previous polynomial approximation algorithms for this problem.     

Value-at-risk estimation by LS-SVR and FS-LS-SVR based on GAS model

ABSTRACT

Conditional risk measuring plays an important role in financial regulation and depends on volatility estimation. A new class of parameter models called Generalized Autoregressive Score (GAS) model has been successfully applied for different error's densities and for different problems of time series prediction in particular for volatility modeling and VaR estimation. To improve the estimating accuracy of the GAS model, this study proposed a semi-parametric method, LS-SVR and FS-LS-SVR applied to the GAS model to estimate the conditional VaR. In particular, we fit the GAS(1,1) model to the return series using three different distributions. Then, LS-SVR and FS-LS-SVR approximate the GAS(1,1) model. An empirical research was performed to illustrate the effectiveness of the proposed method. More precisely, the experimental results from four stock indexes returns suggest that using hybrid models, GAS-LS-SVR and GAS-FS-LS-SVR provides improved performances in the VaR estimation.     

Estimation of the limit variance for sums under a new weak dependence condition

We prove a self-normalized central limit theorem for a mixing class of processes introduced in Kacem M, Loisel S, Maume-Deschamps V. [Some mixing properties of conditionally independent processes. Commun Statist Theory Methods. 2016;45:1241–1259]. This class is larger than more classical strongly mixing processes and thus our result is more general than [Peligrad M, Shao QM. Estimation of the variance of partial sums for ρ-mixing random variables. J Multivar Anal. 1995;52:140–157; Shi S. Estimation of the variance for strongly mixing sequences. Appl Math J Chinese Univ. 2000;15(1):45–54] ones. The fact that some conditionally independent processes satisfy this kind of mixing properties motivated our study. We investigate the weak consistency as well as the asymptotic normality of the estimator of the variance that we propose.     

Exact algorithms for scheduling programs with shared tasks

We study a scheduling problem where the jobs we have to perform are composed of one or more tasks. If two jobs sharing a non-empty subset of tasks are scheduled on the same machine, then these shared tasks have to be performed only once. This kind of problem is known in the literature under the names of VM-PACKING or PAGINATION. Our objective is to schedule a set of these objects on two parallel identical machines, with the aim of minimizing the makespan. This problem is NP-complete as an extension of the PARTITION problem. In this paper we present three exact algorithms with worst-case time-complexity guarantees, by exploring different branching techniques. Our first algorithm focuses on the relation between jobs sharing one or more symbols in common, whereas the two other algorithms branches on the shared symbols.