Upper Bounds on the Covering Number of Galois-Planes with Small Order

Our paper deals with the covering number of finite projective planes which is related to an unsolved question of P. Erdos. An integer linear programming (ILP) formulation of the covering number of finite projective planes is introduced for projective planes of given orders. The mathematical programm...

Full description

Saved in:
Bibliographic Details
Published in:Journal of heuristics 2001-01, Vol.7 (1), p.59
Main Authors: Illes, T, Pisinger, D
Format: Article
Language:English
Subjects:
Heuristic
Integer programming
Linear programming
Mathematical models
Mathematical programming
Studies
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Our paper deals with the covering number of finite projective planes which is related to an unsolved question of P. Erdos. An integer linear programming (ILP) formulation of the covering number of finite projective planes is introduced for projective planes of given orders. The mathematical programming based approach for this problem is new in the area of finite projective planes. Since the ILP problem is {\cal NP}-hard and may involve up to 360.000 boolean variables for the considered problems, we propose a heuristic based on Simulated Annealing. The computational study gives a new insight into the structure of projective planes and their (minimal) blocking sets. This computational study indicates that the current theoretical results may be improved. [PUBLICATION ABSTRACT]
ISSN:1381-1231
1572-9397
DOI:10.1023/A:1026517829321