Filtering algorithms for the NValue constraint

DOI10.1007/S10601-006-9001-9zbMath1114.68064OpenAlexW2039481115MaRDI QIDQ857887

Emmanuel Hebrard, Toby Walsh, Zeynep Kiziltan, Christian Bessiere, Brahim Hnich

Publication date: 5 January 2007

Published in: Constraints (Search for Journal in Brave)

Full work available at URL: https://hal-lirmm.ccsd.cnrs.fr/lirmm-00135540/file/constraints06-nvalue.pdf

zbMATH Keywords

NP-hardpruninglinear relaxationglobal constraints

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (6)

Range and Roots: two common patterns for specifying and propagating counting and occurrence constraints ⋮ Constraint-based large neighborhood search for machine reassignment. A solution approach to the ROADEF/EURO challenge 2012 ⋮ New filtering for \textsc{AtMostNValue} and its weighted variant: a Lagrangian approach ⋮ Guarantees and limits of preprocessing in constraint satisfaction and reasoning ⋮ Filtering AtMostNValue with difference constraints: application to the shift minimisation personnel task scheduling problem ⋮ Parameterized Complexity Results in Symmetry Breaking

Uses Software

• CHIP

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Greed is good: Approximating independent sets in sparse and bounded-degree graphs
• Some eigenvalue properties in graphs (conjectures of Graffiti -- II)
• Hitting sets when the VC-dimension is small
• Improved approximations for maximum independent set via approximation chains
• Principles and Practice of Constraint Programming – CP 2004
• Values of domination numbers of the queen's graph

This page was built for publication: Filtering algorithms for the NValue constraint