Pierre Hansen
BackCahiers du GERAD
369 results — page 7 of 19
A recent comparison of evolutionary, neural network, and scatter search heuristics for solving the p-median problem is completed by (i) gathering or obtaini...
BibTeX reference
The probabilistic satisfiability problem is to verify the consistency of a set of probability values or intervals for logical propositions. The (tight) prob...
BibTeX referenceExact L2-Norm Plane Separation
We consider the problem of separating two sets of points in an n-dimensional real space with a (hyper)plane that minimizes the sum of <i>L</i><sub>2</sub>-n...
BibTeX reference
A set of vertices <i>S</i> in a graph <i>G</i> is independent if no neighbor of a vertex of <i>S</i> belongs to <i>S</i>. A set of vertices <i>U</i> in a gr...
BibTeX reference
This paper presents two new results on the enumeration of all extreme equilibria of the sequence form of a two person extensive game. The sequential form of...
BibTeX reference
The AutoGraphiX 2 system is used to compare the index of a graph <i>G</i> with a number of other graph theoretical invariants, i.e., chromatic number, maxim...
BibTeX referenceVariable Neighborhood Search for Extremal Graphs. 20. Automated Comparison of Graph Invariants
A graph invariant is a function of a graph <i>G</i> which does not depend on labeling of <i>G</i>’s vertices or edges. An algebraic expression of one or sev...
BibTeX reference
Assouad has shown that a real-valued distance <i>d</i> = (<i>d</i><sub><i>ij</i></sub>) <sub>1 ≤ <i>i</i> < <i>j</i> ≤ <i>n</i></sub> is isome...
BibTeX referenceIsoperimetric Polygons of Maximal Width
The value <img src="/cgi-bin/mimetex.cgi?\frac{1}{2n} \cot\left( \frac{\pi}{2n}\right)"> is shown to be an upper bound on the width of any <i>n</i>-sided p...
BibTeX reference
A set of vertices <i>S</i> in a graph <i>G</i> is independent if no neighbor of a vertex of <i>S</i> belongs to <i>S</i>. The independence number &alpha is ...
BibTeX reference
From the pentagon onwards, the area of the regular convex polygon with <i>n</i> sides and unit diameter is greater for each odd number <i>n</i> than for the...
BibTeX reference
We consider four conjectures related to the largest eigenvalue of (the adjacency matrix of) a graph (i.e., to the index of the graph). Three of them have be...
BibTeX referenceVariable Neighborhood Search for Extremal Graphs. 23. On the Randic Index and the Chromatic Number
Let <img src="/cgi-bin/mimetex.cgi?G=(V,E)"> be a simple graph with vertex degrees <img src="/cgi-bin/mimetex.cgi?d1, d2, \ldots, d_n...
BibTeX referenceComparing the Zagreb Indices
Let <img src="/cgi-bin/mimetex.cgi?G=(V,E)"> be a simple graph with <img src="/cgi-bin/mimetex.cgi?n=|V|"> vertices and <img src="/cgi-bin/...
BibTeX reference
Given a simple connected graph <i>G = (V,E)</i> the geodetic closure <i>I [S]</i> <img src="/cgi-bin/mimetex.cgi?\subset"> <i>V</i> of a subset <i>S</i...
BibTeX referenceThe Jackknife Revisited: Feature Selection in Linear Programming Approaches to Credit Scoring
We discuss feature selection approaches within the context of linear programming models for discrimination, with special emphasis on a new interpretation an...
BibTeX reference
The AutoGraphiX research program led to a new type of application of metaheuristics in graph theory, <i>i.e.</i>, finding conjectures on graph invariants by...
BibTeX referenceVariable Neighborhood Search for Extremal Graphs. 18. Conjectures and Results about the Randic Index
Using the AutoGraphiX 2 system (AGX2), we study relations between graph invariants of the form <img src="/cgi-bin/mimetex.cgi?lbn \leq R \oplus i \leq ub...
BibTeX reference
Colour image quantization is a data compression technique that reduces the total set of colours in an image to a representative subset. This problem is expr...
BibTeX reference
We consider the problem of separating two sets of points in an Euclidean space with a hyperplane that minimizes the sum of <i>L<sub>p</sub></i>-norm distanc...
BibTeX reference