ORBi Collection: Mathematics
http://hdl.handle.net/2268/153
The Collection's search engineSearch this channelsearch
http://orbi.ulg.ac.be/simple-search
On the strength of relaxations of multidimensional knapsack problems
http://hdl.handle.net/2268/204060
Title: On the strength of relaxations of multidimensional knapsack problems
<br/>
<br/>Author, co-author: Crama, Yves; Mazzola, Joseph B.
<br/>
<br/>Abstract: Branch-and-bound algorithms for integer programming problems typically employ bounds derived from well-known relaxations, such as the Lagrangian, surrogate, or composite relaxations. Although the bounds derived from these relaxations are stronger than the bound obtained from the linear programming relaxation (LPR), in the case of multidimensional knapsack problems, i.e., integer programming problems with nonnegative objective-function and constraint coefficients, the improvement in the bound that can be realized using these relaxations is limited. In particular, we show that the improvement in the quality of the bound using any of these relaxations cannot exceed the magnitude of the largest coefficient in the objective function, nor can it exceed one-half of the optimal objective-function value of LPR. This implies, for example, that for those problem classes in which all of the objective-function coefficients are equal to 1, the bound derived from the surrogate relaxation cannot be better than the bound obtained by simply rounding the LPR bound. Awareness of these properties is important in the development of algorithms, since this class of problems subsumes many well-known integer programming problems.Berge-acyclic multilinear 0-1 optimization problems
http://hdl.handle.net/2268/204059
Title: Berge-acyclic multilinear 0-1 optimization problems
<br/>
<br/>Author, co-author: Buchheim, Christoph; Crama, Yves; Rodriguez Heck, ElisabethLeaving Gauss: extending Gaussian variance bounds to arbitrary targets
http://hdl.handle.net/2268/204031
Title: Leaving Gauss: extending Gaussian variance bounds to arbitrary targets
<br/>
<br/>Author, co-author: Clette, Emilie; Swan, YvikGeneralized Pascal triangles and binomial coefficients of words
http://hdl.handle.net/2268/203992
Title: Generalized Pascal triangles and binomial coefficients of words
<br/>
<br/>Author, co-author: Stipulanti, Manon
<br/>
<br/>Abstract: We introduce a generalization of Pascal triangle based on binomial coefficients of finite words. These coefficients count the number of times a word appears as a subsequence of another finite word. Similarly to the Sierpinski gasket that can be built as the limit set, for the Hausdorff distance, of a convergent sequence of normalized compact blocks extracted from Pascal triangle modulo 2, we describe and study the first properties of the subset of [0, 1] × [0, 1] associated with this extended Pascal triangle modulo a prime p. From the extended Pascal triangle obtained when p is equal to 2, we derive a sequence of which we study the regularity and the asymptotic behavior of the summatory function. Inspired from this regularity, we extend our results to another famous numeration systems, namely the Zeckendorff numeration system.
<br/>
<br/>Commentary: Work in collaboration with Julien Leroy (ULg, j.leroy@ulg.ac.be) and Michel Rigo (ULg, m.rigo@ulg.ac.be). // Travail en collaboration avec Julien Leroy (ULg, j.leroy@ulg.ac.be) et Michel Rigo (ULg, m.rigo@ulg.ac.be).Relations on words
http://hdl.handle.net/2268/203702
Title: Relations on words
<br/>
<br/>Author, co-author: Rigo, Michel
<br/>
<br/>Abstract: In the first part of this survey, we present classical notions arising in combinatorics on words: growth function of a language, complexity function of an infinite word, pattern avoidance, periodicity and uniform recurrence. Our presentation tries to set up a unified framework with respect to a given binary relation.
In the second part, we mainly focus on abelian equivalence, $k$-abelian equivalence, combinatorial coefficients and associated relations, Parikh matrices and $M$-equivalence. In particular, some new refinements of abelian equivalence are introduced.Le théorème fondamental comme pierre de touche de l'enseignement et de l'apprentissage de l'analyse au secondaire
http://hdl.handle.net/2268/203568
Title: Le théorème fondamental comme pierre de touche de l'enseignement et de l'apprentissage de l'analyse au secondaire
<br/>
<br/>Author, co-author: Balhan, Kevin
<br/>
<br/>Abstract: Using the Anthropological Theory of Didactics and the Theory of Didactic Situations, this thesis brings an answer to several questions of learning the fundamental theorem of the analysis and shows that what prevents to understand it is significant of dysfunctions of the teaching of the analysis at the secondary level in French-speaking Belgium.; A la lumière de la Théorie Anthropologique du Didactique de Chevallard et de la Théorie des Situations Didactiques de Brousseau, la présente thèse apporte un éclairage sur plusieurs questions d'apprentissage du théorème fondamental de l'analyse et montre que ce qui lui fait obstruction est significatif de dysfonctionnements de l'enseignement de l'analyse au niveau secondaire en Belgique Francophone.Robustness of spatial autocorrelation tests
http://hdl.handle.net/2268/203423
Title: Robustness of spatial autocorrelation tests
<br/>
<br/>Author, co-author: Ernst, Marie
<br/>
<br/>Abstract: Spatial autocorrelation expresses the dependence between values at neighbouring locations.
Testing if the spatial autocorrelation is significant may confirm or deny the need to
consider spatial analysis over the classical one. Indeed, the analysis of spatial data is only
meaningful if the spatial components bring information.
Several measures of spatial autocorrelation are defined in the literature. Moran’s index,
Geary’s ratio and Getis-Ord statistic are the most used statistics. Tests based on these
measures have been developed in the literature using asymptotic and permutation results.
They are used in practice in many fields, for instance in geography, economics, biogeosciences,
medicine, ... However, these tests should be cautiously applied because they are
not robust. A single contaminated observation can significantly modify their results.
This poster is composed of two parts. Firstly, the robustness of already available tools
for measuring spatial autocorrelation will be analysed. Secondly, alternative methods will
be proposed to robustly test the spatial autocorrelation.Topos de Grothendieck et fonctions holomorphes tempérées
http://hdl.handle.net/2268/202919
Title: Topos de Grothendieck et fonctions holomorphes tempérées
<br/>
<br/>Author, co-author: Dubussy, Christophe
<br/>
<br/>Abstract: Dans les années 60, Grothendieck révolutionna la géométrie algébrique en introduisant le concept de topos. Faisant face à des situations où la notion d'ouvert était trop restrictive pour comprendre les phénomènes géométriques sous-jacents, il définit une nouvelle notion de topologie dans le langage de la théorie des catégories. Très utilisée pour résoudre des problèmes de géométrie et d'analyse contemporains, cette notion a aussi de nombreuses applications surprenantes en logique (théorie intuitionniste, équivalence de Morita, etc ...).
Dans ce séminaire je proposerai une application de la théorie des topos de Grothendieck pour étudier les fonctions et les distributions tempérées. En effet, ces objets ne forment un faisceau que sur une topologie de Grothendieck particulière (la topologie sous-analytique), qui n'est pas une topologie au sens usuel du terme. Je montrerai alors, de manière abstraite, comment définir un faisceau de fonctions holomorphes tempérées qui a joué un rôle crucial dans la démonstration de la correspondance de Riemann-Hilbert (généralisation du 21ème problème d'Hilbert). En particulier, ce nouveau faisceau fournira une nouvelle définition, presque purement algébrique, des distributions de Schwartz.Production Planning in Automated Manufacturing
http://hdl.handle.net/2268/202760
Title: Production Planning in Automated Manufacturing
<br/>
<br/>Author, co-author: Crama, Yves; Oerlemans, Alwin G.; Spieksma, Frits C.R.The polytope of block diagonal matrices and complete bipartite partitionings
http://hdl.handle.net/2268/202758
Title: The polytope of block diagonal matrices and complete bipartite partitionings
<br/>
<br/>Author, co-author: Crama, Yves; Oosten, Maarten
<br/>
<br/>Abstract: Motivated by a fundamental clustering problem arising in several areas (production management, marketing, numerical analysis, etc.), we investigate the facial structure of the polytope whose extreme points are all 0–1 block diagonal matrices. For this polytope, general properties of facet-defining inequalities are investigated and specific families of facets are identified. Various techniques for lifting or combining facet-defining inequalities into new ones are also presented. Throughout the paper, a block diagonal matrix is regarded as the adjacency matrix of a disjoint union of complete bipartite graphs. The presentation and the derivation of the results heavily rely on this graph-theoretic interpretation.Robust discriminant analysis based on the joint graphcial lasso estimator
http://hdl.handle.net/2268/202654
Title: Robust discriminant analysis based on the joint graphcial lasso estimator
<br/>
<br/>Author, co-author: Aerts, Stéphanie; Croux, Christophe; Wilms, Ines
<br/>
<br/>Abstract: Linear and Quadratic Discriminant Analysis (LDA/QDA) are the most often applied classification rules under the normality assumption. When there is not enough data, the quadratic rule, which requires the estimation of one precision matrix in each class, is often replaced by the linear one, based on the homoscedasticity assumption. This strong assumption is however rarely verified in practice and ignores the intrinsic différences between groups that may be of particular interest in the classification context. In this aper, alternatives to the usual maximum likelihood estimates for the precision matrices are proposed that borrow strength across classes while allowing for heterogeneity at the same time. This results in a classifier that is intermediate between QDA and LDA. Moreover, our estimator is sparse: the undesirable effect of uninformative variables is reduced. The performance of the method is illustrated through simulated and real dataset
examples.A full inference toolbox to measure multivariate relative dispersion
http://hdl.handle.net/2268/202653
Title: A full inference toolbox to measure multivariate relative dispersion
<br/>
<br/>Author, co-author: Aerts, Stéphanie; Haesbroeck, Gentiane
<br/>
<br/>Abstract: In the univariate context, coefficients of variation (CV) are widely used to compare the dispersion of a variable in several populations. When the comparison is based on p characteristics however, side-by-side comparison of marginal CV’s may lead to contradictions. In this talk, we present a multivariate coefficient of variation (MCV), defined as the inverse of the Mahalanobis distance between the mean and the origin, whose usefulness is demonstrated in some applications in finance and analytical chemistry. A full inference toolbox is provided for practitioners: several parametric and non-parametric bias-correction methods are suggested and compared, and some exact and approximate confidence intervals are built and analyzed in a simulation study. Finally, in order to meet the practical need to compare MCV’s in K populations, some asymptotic statistical testing procedures are derived, whose finite-sample performance is empirically assessed.
Throughout the talk, the robustness of the techniques will be discussed. As a by-product, a test statistic allowing to reliably compare K univariate CV’s even in presence of outliers will be outlined.Hitting or avoiding balls in Euclidean space
http://hdl.handle.net/2268/202636
Title: Hitting or avoiding balls in Euclidean space
<br/>
<br/>Author, co-author: Crama, Yves; Ibaraki, Toshihide
<br/>
<br/>Abstract: We investigate the algorithmic complexity of several geometric problems of the following type: given a "feasible" box and a collection of balls in Euclidean space, find a feasible point which is covered by as few or, respectively, by as many balls as possible. We establish that all these problems are NP-hard in their most general version. We derive tight lower and upper bounds on the complexity of their one-dimensional versions. Finally, we show that all these problems can be solved in polynomial time when the dimension of the space is fixed.Variable and term removal from Boolean formulae
http://hdl.handle.net/2268/202634
Title: Variable and term removal from Boolean formulae
<br/>
<br/>Author, co-author: Crama, Yves; Ekin, Oya; Hammer, Peter L.
<br/>
<br/>Abstract: Given a Boolean formula in disjunctive normal form, the variable deletion control set problem consists in finding a minimum cardinality set of variables whose deletion from the formula results in a DNF satisfying some prescribed property. Similar problems can be defined with respect to the fixation of variables or the deletion of terms in a DNF. In this paper, we investigate the complexity of such problems for a broad class of DNF properties.Une construction des nombres hyperréels
http://hdl.handle.net/2268/202578
Title: Une construction des nombres hyperréels
<br/>
<br/>Author, co-author: Nicolay, Samuel
<br/>
<br/>Abstract: Nous proposons ici une brève construction classique des nombres hyperréels à partir des nombres réels. Dans un soucis de pédagogie, nous omettons les détails les plus techniques. La présentation est divisée en deux parties. La première fait presqu' exclusivement appel à l'intuition, tandis que la seconde reprend les mêmes linéaments mais se veut plus rigoureuse.Abelian borders and periodicity
http://hdl.handle.net/2268/202438
Title: Abelian borders and periodicity
<br/>
<br/>Author, co-author: Charlier, EmiliePseudo-Boolean optimization
http://hdl.handle.net/2268/202427
Title: Pseudo-Boolean optimization
<br/>
<br/>Author, co-author: Crama, Yves; Hammer, Peter L.
<br/>
<br/>Abstract: This article briefly surveys some fundamental results regarding pseudo-Boolean functions.Boolean normal forms, shellability and reliability computations
http://hdl.handle.net/2268/202426
Title: Boolean normal forms, shellability and reliability computations
<br/>
<br/>Author, co-author: Boros, Endre; Crama, Yves; Ekin, Oya; Hammer, Peter L.; Ibaraki, Toshihide; Kogan, Alex
<br/>
<br/>Abstract: Orthogonal forms of positive Boolean functions play an important role in reliability theory, since the probability that they take value 1 can be easily computed. However, few classes of disjunctive normal forms are known for which orthogonalization can be efficiently performed. An interesting class with this property is the class of shellable disjunctive normal forms (DNFs). In this paper, we present some new results about shellability. We establish that every positive Boolean function can be represented by a shellable DNF, we propose a polynomial procedure to compute the dual of a shellable DNF, and we prove that testing the so-called lexico-exchange (LE) property (a strengthening of shellability) is NP-complete.Inference in a stochastic SEIR model using Sequential Monte Carlo methods
http://hdl.handle.net/2268/202086
Title: Inference in a stochastic SEIR model using Sequential Monte Carlo methods
<br/>
<br/>Author, co-author: Bonou, Wilfried; LAMBERT, Philippe
<br/>
<br/>Abstract: Many biological, physical, chemical, economic, and social phenomena are dynamic and are modeled using (systems of) Ordinary Differential Equations (ODEs). But a more realistic way to describe these dynamics relies on Discrete Time Markov Chains (DTMC). There is a growing interest in the development of Bayesian statistical methods to infer on the parameters in such dynamic models, particularly those defining epidemic spread, by combining prior information with experimental or observational data. Our proposal aims to explore the merits of the Bayesian Optimal Filtering technique in the estimation of the parameters of a stochastic SEIR (S = Susceptible, E = Exposed, I = Infectious, R = Removed) epidemic model. State Space Models (SSMs) are used to describe the epidemic dynamic. The unknown static parameters are estimated using a combination of Sequential Monte Carlo techniques with a Markov Chain Monte Carlo algorithm, . . .IT formulae for gamma target: mutual information and relative entropy
http://hdl.handle.net/2268/201799
Title: IT formulae for gamma target: mutual information and relative entropy
<br/>
<br/>Author, co-author: Arras, Benjamin; Swan, Yvik