Result: Clutter nonidealness

Title:
Clutter nonidealness
Authors:
ARGIROFFO, G, BIANCHI, S, NASINI, G
Source:
2nd Cologne/Twente Workshop on Graphs and Combinatorial Optimization (CTW 2003), Enschede, The Netherlands, May 14-16, 2003Discrete applied mathematics. 154(9):1324-1334
Publisher Information:
Amsterdam; Lausanne; New York, NY: Elsevier, 2006.
Publication Year:
2006
Physical Description:
print, 13 ref
Original Material:
INIST-CNRS
Subject Terms:
Control theory, operational research, Automatique, recherche opérationnelle, Computer science, Informatique, Mathematics, Mathématiques, Sciences exactes et technologie, Exact sciences and technology, Sciences et techniques communes, Sciences and techniques of general use, Mathematiques, Mathematics, Combinatoire. Structures ordonnées, Combinatorics. Ordered structures, Combinatoire, Combinatorics, Plans d'expériences et configurations, Designs and configurations, Analyse numérique. Calcul scientifique, Numerical analysis. Scientific computation, Analyse numérique, Numerical analysis, Méthodes numériques en programmation mathématique, optimisation et calcul variationnel, Numerical methods in mathematical programming, optimization and calculus of variations, Sciences appliquees, Applied sciences, Informatique; automatique theorique; systemes, Computer science; control theory; systems, Informatique théorique, Theoretical computing, Algorithmique. Calculabilité. Arithmétique ordinateur, Algorithmics. Computability. Computer arithmetics, Fouillis écho, Clutter, Confusión eco, Informatique théorique, Computer theory, Informática teórica, Optimisation combinatoire, Combinatorial optimization, Optimización combinatoria, Polytope, Politope, Problème recouvrement, Covering problem, Problema recubrimiento, Programmation en nombres entiers, Integer programming, Programación entera, Programmation mathématique, Mathematical programming, Programación matemática, Recouvrement ensemble, Set covering, Cubierta conjunto, Image fond, Programmation combinatoire, Clutters, Nonidealness index
Document Type:
Conference Conference Paper
File Description:
text
Language:
English
Author Affiliations:
Depto. de Matemática. Facuttad de Ciencias Exactas, Ingeniería y Agrimensura, Universidad Nacional de Rosario, Argentina
ISSN:
0166-218X
Access URL:
http://pascal-francis.inist.fr/vibad/index.php?action=search&terms=17737554
Rights:
Copyright 2006 INIST-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
Notes:
Computer science; theoretical automation; systems

Mathematics
Accession Number:
edscal.17737554
Database:
PASCAL Archive

Further Information

Several key results for set packing problems do not seem to be easily or even possibly transferable to set covering problems, although the symmetry between them. The goal of this paper is to introduce a nonidealness index by transferring the ideas used for the imperfection index defined by Gerke and McDiarmid [Graph imperfection, J. Combin. Theory Ser. B 83 (2001) 58-78]. We found a relationship between the two indices and the strength of facets defined in [M. Goemans, Worst-case comparison of valid inequalities for the TSP, mathematical programming, in: Fifth Integer Programming and Combinatorial Optimization Conference, Lecture Notes in Computer Science, vol. 1084, Vancouver, Canada, 1996, pp. 415-429; M. Goemans, L.A. Hall, The strongest facets of the acyclic subgraph polytope are unknown, in: Integer Programming and Combinatorial Optimization, Lecture Notes in Computer Science, vol. 1084, Springer, Berlin, 1996, pp. 415-429]. We prove that a clutter is as nonideal as its blocker and find some other properties that could be transferred from the imperfection index to the nonidealness index. Finally, we analyze the behavior of the nonidealness index under some clutter operations.