Filtering Algorithms for the Nvalue Constraint
| dc.contributor.author | Bessiere, Christian | |
| dc.contributor.author | Hebrard, Emmanuel | |
| dc.contributor.author | Hnich, Brahim | |
| dc.contributor.author | Kiziltan, Zeynep | |
| dc.contributor.author | Walsh, Toby | |
| dc.date.accessioned | 2023-06-16T12:47:54Z | |
| dc.date.available | 2023-06-16T12:47:54Z | |
| dc.date.issued | 2006 | |
| dc.description | 2nd International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems -- MAY 30-JUN 01, 2005 -- Prague, CZECH REPUBLIC | en_US |
| dc.description.abstract | The NVALUE constraint counts the number of different values assigned to a vector of variables. Propagating generalized arc consistency on this constraint is NP-hard. We show that computing even the lower bound on the number of values is NP-hard. We therefore study different approximation heuristics for this problem. We introduce three new methods for computing a lower bound on the number of values. The first two are based on the maximum independent set problem and are incomparable to a previous approach based on intervals. The last method is a linear relaxation of the problem. This gives a tighter lower bound than all other methods, but at a greater asymptotic cost. | en_US |
| dc.description.sponsorship | Charles Univ, Fac Math & Phys,Act M Agcy,ARTIST,Carmen Syst,CoLogNet,Intelligent Informat Syst Inst,ILOG SA,SICS | en_US |
| dc.identifier.doi | 10.1007/s10601-006-9001-9 | |
| dc.identifier.issn | 1383-7133 | |
| dc.identifier.issn | 1572-9354 | |
| dc.identifier.scopus | 2-s2.0-33751507679 | |
| dc.identifier.uri | https://doi.org/10.1007/s10601-006-9001-9 | |
| dc.identifier.uri | https://hdl.handle.net/20.500.14365/904 | |
| dc.language.iso | en | en_US |
| dc.publisher | Springer | en_US |
| dc.relation.ispartof | Constraınts | en_US |
| dc.rights | info:eu-repo/semantics/openAccess | en_US |
| dc.subject | NVALUE constraint | en_US |
| dc.subject | NP-hard | en_US |
| dc.subject | ATLEASTNVALUE | en_US |
| dc.subject | ATMOSTNVALUE | en_US |
| dc.subject | pruning | en_US |
| dc.subject | linear relaxation | en_US |
| dc.subject | global constraints | en_US |
| dc.title | Filtering Algorithms for the Nvalue Constraint | en_US |
| dc.type | Conference Object | en_US |
| dspace.entity.type | Publication | |
| gdc.author.id | Walsh, Toby/0000-0003-2998-8668 | |
| gdc.author.id | Hebrard, Emmanuel/0000-0003-3131-0709 | |
| gdc.author.id | Hnich, Brahim/0000-0001-8875-8390 | |
| gdc.author.scopusid | 6701546627 | |
| gdc.author.scopusid | 55897451800 | |
| gdc.author.scopusid | 6602458958 | |
| gdc.author.scopusid | 55962417500 | |
| gdc.author.scopusid | 55806690200 | |
| gdc.author.wosid | Hnich, Brahim/B-4435-2010 | |
| gdc.author.wosid | Walsh, Toby/Q-9043-2016 | |
| gdc.bip.impulseclass | C4 | |
| gdc.bip.influenceclass | C4 | |
| gdc.bip.popularityclass | C5 | |
| gdc.coar.access | open access | |
| gdc.coar.type | text::conference output | |
| gdc.collaboration.industrial | false | |
| gdc.description.department | İzmir Ekonomi Üniversitesi | en_US |
| gdc.description.departmenttemp | CNRS, LIRMM, F-34392 Montpellier, France; Univ New S Wales, Natl ICT Australia Ltd, Sydney, NSW 1466, Australia; Izmir Univ Econ, TR-35330 Izmir, Turkey; Univ Bologna, I-40136 Bologna, Italy | en_US |
| gdc.description.endpage | 293 | en_US |
| gdc.description.issue | 4 | en_US |
| gdc.description.publicationcategory | Konferans Öğesi - Uluslararası - Kurum Öğretim Elemanı | en_US |
| gdc.description.scopusquality | Q3 | |
| gdc.description.startpage | 271 | en_US |
| gdc.description.volume | 11 | en_US |
| gdc.description.wosquality | Q3 | |
| gdc.identifier.openalex | W2039481115 | |
| gdc.identifier.wos | WOS:000242421900002 | |
| gdc.index.type | WoS | |
| gdc.index.type | Scopus | |
| gdc.oaire.accesstype | BRONZE | |
| gdc.oaire.diamondjournal | false | |
| gdc.oaire.impulse | 6.0 | |
| gdc.oaire.influence | 7.1496054E-9 | |
| gdc.oaire.isgreen | true | |
| gdc.oaire.keywords | [INFO.INFO-AI] Computer Science [cs]/Artificial Intelligence [cs.AI] | |
| gdc.oaire.keywords | NVALUE CONSTRAINT; NP-HARD; PRUNING; LINEAR RELAXATION; GLOBAL CONSTRAINTS | |
| gdc.oaire.keywords | Linear relaxation | |
| gdc.oaire.keywords | NValue constraint | |
| gdc.oaire.keywords | . | |
| gdc.oaire.keywords | NP-hard | |
| gdc.oaire.keywords | AtMostNValue | |
| gdc.oaire.keywords | Pruning | |
| gdc.oaire.keywords | AtleastNValue | |
| gdc.oaire.keywords | Global constraints | |
| gdc.oaire.keywords | Analysis of algorithms and problem complexity | |
| gdc.oaire.keywords | pruning | |
| gdc.oaire.keywords | global constraints | |
| gdc.oaire.keywords | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) | |
| gdc.oaire.keywords | linear relaxation | |
| gdc.oaire.keywords | Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) | |
| gdc.oaire.popularity | 3.2183247E-9 | |
| gdc.oaire.publicfunded | true | |
| gdc.oaire.sciencefields | 0102 computer and information sciences | |
| gdc.oaire.sciencefields | 02 engineering and technology | |
| gdc.oaire.sciencefields | 01 natural sciences | |
| gdc.oaire.sciencefields | 0202 electrical engineering, electronic engineering, information engineering | |
| gdc.openalex.collaboration | International | |
| gdc.openalex.fwci | 2.2355 | |
| gdc.openalex.normalizedpercentile | 0.89 | |
| gdc.openalex.toppercent | TOP 10% | |
| gdc.opencitations.count | 16 | |
| gdc.plumx.crossrefcites | 14 | |
| gdc.plumx.mendeley | 7 | |
| gdc.plumx.scopuscites | 34 | |
| gdc.scopus.citedcount | 34 | |
| gdc.wos.citedcount | 25 | |
| relation.isOrgUnitOfPublication | e9e77e3e-bc94-40a7-9b24-b807b2cd0319 | |
| relation.isOrgUnitOfPublication.latestForDiscovery | e9e77e3e-bc94-40a7-9b24-b807b2cd0319 |
Files
Original bundle
1 - 1 of 1