ORBi Collection: Mathematics
http://hdl.handle.net/2268/153
The Collection's search engineSearch this channelsearch
http://orbi.ulg.ac.be/simple-search
Counting Subwords Occurrences in Base-b Expansions
http://hdl.handle.net/2268/218185
Title: Counting Subwords Occurrences in Base-b Expansions
<br/>
<br/>Author, co-author: Leroy, Julien; Rigo, Michel; Stipulanti, ManonFri, 12 Jan 2018 14:53:39 GMTA set of sequences of complexity $2n+1$
http://hdl.handle.net/2268/217915
Title: A set of sequences of complexity $2n+1$
<br/>
<br/>Author, co-author: Cassaigne, Julien; Labbé, Sébastien; Leroy, JulienMon, 08 Jan 2018 15:51:16 GMTUne synergie à double sens entre recherche et formation : l’empirisme comme obstacle à la réflexivité
http://hdl.handle.net/2268/217792
Title: Une synergie à double sens entre recherche et formation : l’empirisme comme obstacle à la réflexivité
<br/>
<br/>Author, co-author: Balhan, Kevin; Schneider, Maggy
<br/>
<br/>Abstract: L’empirisme est ici envisagé sous un double point de vue : celui des obstacles d’apprentissage en mathématique et celui des pratiques enseignantes. Ce double regard, issu de recherches distinctes, nous amène à identifier un frein à la posture de praticien réflexif que vise la formation des enseignants en Belgique pour faire des formés, des vecteurs de changement. Il s’agit de la résistance des pratiques ostensives dont les futurs professeurs de Lycée seraient dupes en raison de leur rapport empirique aux concepts mathématiques, ici le concept de limite.Fri, 05 Jan 2018 21:58:06 GMTAn introduction to the ELECTRE research programme
http://hdl.handle.net/2268/217620
Title: An introduction to the ELECTRE research programme
<br/>
<br/>Author, co-author: Crama, Yves; Hansen, Pierre
<br/>
<br/>Abstract: The discrete multicriteria decision problem has attracted a large amount of attention during the last 15 years. In contrast with multi-attribute utility theory, prevailing in the U.S., a series of methods have been developped in Europe, mostly by Roy and his co-workers, under the name ELECTRE. The present paper is devoted to an overview of that research programme.Tue, 02 Jan 2018 16:23:50 GMTLocal search in combinatorial optimization
http://hdl.handle.net/2268/217618
Title: Local search in combinatorial optimization
<br/>
<br/>Author, co-author: Crama, Yves; Kolen, Anton W.J.; Pesch, ErwinTue, 02 Jan 2018 16:06:10 GMTAnalysis of STEM-like solutions to multi-objective programming problems
http://hdl.handle.net/2268/217604
Title: Analysis of STEM-like solutions to multi-objective programming problems
<br/>
<br/>Author, co-author: Crama, YvesTue, 02 Jan 2018 13:35:54 GMTStrong unimodularity for matrices and hypergraphs
http://hdl.handle.net/2268/217600
Title: Strong unimodularity for matrices and hypergraphs
<br/>
<br/>Author, co-author: Crama, Yves; Hammer, Peter L.; Ibaraki, Toshihide
<br/>
<br/>Abstract: A 0–1 matrix A is called strongly unimodular if all the bases of (A, I) are triangular. We develop equivalent conditions for strong unimodularity, first in algebraic, then in graph theoretic terms. This provides a link with the theory of unimodular and balanced hypergraphs, and allows us to produce a polynomial-time recognition algorithm for strongly unimodular matrices. We consider next the constraint matrix of the problem obtained by linearizing a general, unconstrained optimization problem in 0–1 variables. Because that matrix has 0, 1 and −1 entries, we are led to introduce the concept of signed hypergraph in which every edge is affected of a positive or negative sign. Our results on strong unimodularity are extended to the class of signed hypergraphs.Tue, 02 Jan 2018 12:32:00 GMTDualization of regular boolean functions
http://hdl.handle.net/2268/217599
Title: Dualization of regular boolean functions
<br/>
<br/>Author, co-author: Crama, Yves
<br/>
<br/>Abstract: A monotonic Boolean function is regular if its variables are naturally ordered by decreasing ‘strength’, so that shifting to the right the non-zero entries of any binary false point always yields another false point. Peled and Simeone recently published a polynomial algorithm to generate the maximal false points (MFP's) of a regular function from a list of its minimal true points (MTP's). Another efficient algorithm for this problem is presented here, based on a characterization of the MFP's of a regular function in terms of its MTP's. This result is also used to derive a new upper bound on the number of MFP's of a regular function.Tue, 02 Jan 2018 12:24:41 GMTProduct form parametric representation of the solutions to a quadratic boolean equation
http://hdl.handle.net/2268/217598
Title: Product form parametric representation of the solutions to a quadratic boolean equation
<br/>
<br/>Author, co-author: Crama, Yves; Hammer, Peter L.; Jaumard, Brigitte; Simeone, Bruno
<br/>
<br/>Abstract: A parametric représentation of the solutions to a consistent quadratic boolean equation in n variables is obtained. Each variable (or its complement) is expressed as a product of free boolean parameters or their complements. These expressions provide a complete description of the solution set of the equation. An O (n^3) algorithm is proposed to produce such a representation. An application to the maximization of some classes of pseudoboolean functions is discussed.Tue, 02 Jan 2018 12:17:25 GMTBimatroidal independence systems
http://hdl.handle.net/2268/217452
Title: Bimatroidal independence systems
<br/>
<br/>Author, co-author: Crama, Yves; Hammer, Peter L.
<br/>
<br/>Abstract: An independence system Σ=(X, F) is called bimatroidal if there exist two matroids M=(X,FM) and N=(X,FN) such that F=FM∪FN. When this is the case, {M,N} is called a bimatroidal decomposition of Σ. This paper initiates the study of bimatroidal systems. Given the collection of circuits of an arbitrary independence system Σ (or, equivalently, the constraints of a set-covering problem), we address the following question: does Σ admit a bimatroidal decomposition {M,N} and, if so, how can we actually produce the circuits of M andN? We derive a number of results concerning this problem, and we present a polynomial time algorithm to solve it when every two circuits of Σ have at most one common element. We also propose different polynomial time algorithms for set covering problems defined on the circuit-set of bimatroidal systems.Mon, 25 Dec 2017 19:52:18 GMTRecognition problems for special classes of polynomials in 0-1 variables
http://hdl.handle.net/2268/217451
Title: Recognition problems for special classes of polynomials in 0-1 variables
<br/>
<br/>Author, co-author: Crama, Yves
<br/>
<br/>Abstract: This paper investigates the complexity of various recognition problems for pseudo-Boolean functions (i.e., real-valued functions defined on the unit hypercube B^n = {0,1}^n), when such functions are represented as multilinear polynomials in their variables. Determining whether a pseudo-Boolean function (a) is monotonic, or (b) is supermodular, or (c) is threshold, or (d) has a unique local maximum in each face of B^n, or (e) has a unique local maximum in B^n, is shown to be NP-hard. A polynomial-time recognition algorithm is presented for unimodular functions, previously introduced by Hansen and Simeone as a class of functions whose maximization over B^n is reducible to a network minimum cut problem.Mon, 25 Dec 2017 19:39:52 GMTRecognition of quadratic graphs and adjoints of bidirected graphs
http://hdl.handle.net/2268/217450
Title: Recognition of quadratic graphs and adjoints of bidirected graphs
<br/>
<br/>Author, co-author: Crama, Yves; Hammer, Peter L.Mon, 25 Dec 2017 19:29:33 GMTA characterization of a cone of pseudo-Boolean functions via supermodularity-type inequalities
http://hdl.handle.net/2268/217428
Title: A characterization of a cone of pseudo-Boolean functions via supermodularity-type inequalities
<br/>
<br/>Author, co-author: Crama, Yves; Hammer, Peter L.; Holzman, Ron
<br/>
<br/>Abstract: A pseudo-Boolean function is a real valued function defined on the vertices of the unit n-dimensional hypercube. It has a unique expression as a multilinear polynomial in n variables. It is called almost-positive if all the coefficients in that expression, except maybe those in the linear part, are nonnegative. The almost-positive functions form a convex cone, given explicitly by its extreme rays. Here we describe this cone by a system of linear inequalities, which can be viewed as a natural generalization of supermodularity to higher orders. We also point out a characterization in terms of the sign of partial derivatives.Sun, 24 Dec 2017 11:39:20 GMTUpper-bounds for quadratic 0-1 maximization
http://hdl.handle.net/2268/217426
Title: Upper-bounds for quadratic 0-1 maximization
<br/>
<br/>Author, co-author: Boros, Endre; Crama, Yves; Hammer, Peter L.
<br/>
<br/>Abstract: In this paper, three different approaches are generalised to obtain upper bounds for the maximum of a quadratic pseudo-Boolean function f over [0,1]^n. The original approaches (complementation, majorization and linearization) were introduced by Hammer, Hansen and Simeone. The generalization in this paper yields three upper bounds, Ck, Mk and Lk for each integer k ⩾ 2, where Cn = Ln = Mn is the maximum of f, and C2 = L2 = M2 is the roof duality bound studied by Hammer, Hansen and Simeone. It is proved that Ck = Mk = Lk for all values of k.Sun, 24 Dec 2017 11:20:44 GMTPacking, covering and partitioning problems with strongly unimodular constraint matrices
http://hdl.handle.net/2268/217424
Title: Packing, covering and partitioning problems with strongly unimodular constraint matrices
<br/>
<br/>Author, co-author: Crama, Yves; Hammer, Peter L.; Ibaraki, Toshihide
<br/>
<br/>Abstract: A 0-1 matrix A is called strongly unimodular if all its nonsingular square submatrices are
triangular. We present an efficient algorithm for linear programming problems in binary
variables, when all constraints are of the packing, covering or partitioning type, and the
constraint matrix is strongly unimodular. The algorithm uses a certain decomposition of
strongly unimodular matrices into their so-called "restricted unimodular" components, and an
efficient optimization algorithm for linear programs with restricted unimodular cosntraints.Sun, 24 Dec 2017 09:43:07 GMTMore characterizations of triangulated graphs
http://hdl.handle.net/2268/217422
Title: More characterizations of triangulated graphs
<br/>
<br/>Author, co-author: Benzaken, Claude; Crama, Yves; Duchet, Pierre; Hammer, Peter L.; Maffray, Frédéric
<br/>
<br/>Abstract: New characterizations of triangulated and cotriangulated graphs are presented. Cotriangulated graphs form a natural subclass of the class of strongly perfect graphs, and they are also characterized in terms of the shellability of some associated collection of sets. Finally, the notion of stability function of a graph is introduced, and it is proved that a graph is triangulated if and only if the polynomial representing its stability function has all its coefficients equal to 0, +1 or −1.Sat, 23 Dec 2017 18:48:04 GMTThe basic algorithm for pseudo-Boolean programming revisited
http://hdl.handle.net/2268/217421
Title: The basic algorithm for pseudo-Boolean programming revisited
<br/>
<br/>Author, co-author: Crama, Yves; Hansen, Pierre; Jaumard, Brigitte
<br/>
<br/>Abstract: The basic algorithm of pseudo-Boolean programming due to Hammer and Rudeanu allows to minimize nonlinear 0–1 functions by recursively eliminating one variable at each iteration. We show it has linear-time complexity when applied to functions associated in a natural way with graphs of bounded tree-width. We also propose a new approach to the elimination of a variable based on a branch-and-bound scheme, which allows shortcuts in Boolean manipulations. Computational results are reported on.Sat, 23 Dec 2017 18:32:40 GMTPolynomial-time inference of all valid implications for Horn and related formulae
http://hdl.handle.net/2268/217419
Title: Polynomial-time inference of all valid implications for Horn and related formulae
<br/>
<br/>Author, co-author: Boros, Endre; Crama, Yves; Hammer, Peter L.
<br/>
<br/>Abstract: This paper investigates the complexity of a general inference problem: given a propositional formula in conjunctive normal form, find all prime implications of the formula. Here, a prime implication means a minimal clause whose validity is implied by the validity of the formula. We show that, under some reasonable assumptions, this problem can be solved in time polynomially bounded in the size of the input and in the number of prime implications. In the case of Horn formulae, the result specializes to yield an algorithm whose complexity grows only linearly with the number of prime implications. The result also applies to a class of formulae generalizing both Horn and quadratic formulae.Sat, 23 Dec 2017 17:36:02 GMTDetection of spurious states of neural networks
http://hdl.handle.net/2268/217417
Title: Detection of spurious states of neural networks
<br/>
<br/>Author, co-author: Crama, Yves; Hansen, Pierre; Jaumard, Brigitte
<br/>
<br/>Abstract: The authors study the complexity and propose an algorithm for the problem of determining, given p vectors of {-1,1}^n, all linear combinations of them which are also in {-1,1}^n. Computational results are reported. This problem corresponds to the detection of spurious states in neural networks.Sat, 23 Dec 2017 11:26:22 GMTApproximation algorithms for three-dimensional assignment problems with triangle inequalities
http://hdl.handle.net/2268/217339
Title: Approximation algorithms for three-dimensional assignment problems with triangle inequalities
<br/>
<br/>Author, co-author: Crama, Yves; Spieksma, Frits C.R.
<br/>
<br/>Abstract: The three-dimensional assignment problem (3DA) is defined as follows. Given are three disjoint n-sets of points, and nonnegative costs associated with every triangle consisting of exactly one point from each set. The problem is to find a minimum-weight collection of n triangles covering each point exactly once. We consider the special cases of 3DA where a distance (verifying the triangle inequalities) is defined on the set of points, and the cost of a triangle is either the sum of the lengths of its sides (problem TΔ ) or the sum of the lengths of its two shortest sides (problem SΔ ). We prove that TΔ and SΔ are NP-hard. For both TΔ and SΔ , we present 1/2- and 1/3-approximate algorithms, i.e. heuristics which always deliver a feasible solution whose cost is at most 3/2, resp. 4/3, of the optimal cost. Computational experiments indicate that the performance of these heuristics is excellent on randomly generated instances of TΔ and SΔ .Thu, 21 Dec 2017 12:56:56 GMT