Indexing metadata

On Computing Minimal Correction Subsets


 
Dublin Core PKP Metadata Items Metadata for this Document
 
1. Title Title of document On Computing Minimal Correction Subsets
 
2. Creator Author's name, affiliation, country Joao Marques-Silva; University College Dublin; Ireland
 
2. Creator Author's name, affiliation, country Federico Heras; University College Dublin; Ireland
 
2. Creator Author's name, affiliation, country Mikolas Janota; INESC-ID; Portugal
 
2. Creator Author's name, affiliation, country Alessandro Previti; University College Dublin; Ireland
 
2. Creator Author's name, affiliation, country Anton Belov; University College Dublin; Ireland
 
3. Subject Discipline(s) Artificial Intelligence, Computer Science
 
3. Subject Keyword(s) Boolean Satisfiability; Over-Constrained Systems; Minimal Correction Subsets; MCSes
 
4. Description Abstract A set of constraints that cannot be simultaneously satisfied is over-constrained. Minimal relaxations and minimal explanations for over-constrained problems find many practical uses. For Boolean formulas, minimal relaxations of over-constrained problems are referred to as Minimal Correction Subsets (MCSes). MCSes find many applications, including the enumeration of MUSes. Existing approaches for computing MCSes either use a Maximum Satisfiability (MaxSAT) solver or iterative calls to a Boolean Satisfiability (SAT) solver. This paper shows that existing algorithms for MCS computation can be inefficient, and so inadequate, in certain practical settings. To address this problem, this paper develops a number of novel techniques for improving the performance of existing MCS computation algorithms. More importantly, the paper proposes a novel algorithm for computing MCSes. Both the techniques and the algorithm are evaluated empirically on representative problem instances, and are shown to yield the most efficient and robust solutions for MCS computation.
 
5. Publisher Organizing agency, location
 
6. Contributor Sponsor(s) SFI, Ireland; FCT, Portugal
 
7. Date (YYYY-MM-DD) 2013-06-29
 
8. Type Status & genre Peer-reviewed Paper
 
8. Type Type
 
9. Format File format PDF
 
10. Identifier Universal Resource Indicator https://www.aaai.org/ocs/index.php/IJCAI/IJCAI13/paper/view/6922
 
11. Source Journal/conference title; vol., no. (year) International Joint Conference on Artificial Intelligence; Twenty-Third International Joint Conference on Artificial Intelligence
 
12. Language English=en en
 
14. Coverage Geo-spatial location, chronological period, research sample (gender, age, etc.)
 
15. Rights Copyright and permissions

Authors who submit to this conference agree to the following terms:

a)Authors transfer their copyrights in their paper to the International Joint Conferences on Artificial Intelligence, Inc. (IJCAI), in order to deal with future requests for reprints, translations, anthologies, reproductions, excerpts, and other publications. This grant will include, without limitation, the entire copyright in the paper in all countries of the world, including all renewals, extensions, and reversions thereof, whether such rights currently exist or hereafter come into effect, and also the exclusive right to create electronic versions of the paper, to the extent that such right is not subsumed under copyright.

b)Every named author warrants that he/she is the sole author and owner of the copyright in the paper, except for those portions shown to be in quotations; that the paper is original throughout; and that their right to make the grants set forth above is complete and unencumbered. If anyone brings any claim or action alleging facts that, if true, constitute a breach of any of the foregoing warranties, each author, individually and collectively, will hold harmless and indemnify IJCAI, their grantees, their licensees, and their distributors against any liability, whether under judgment, decree, or compromise, and any legal fees and expenses arising out of that claim or actions, and the undersigned will cooperate fully in any defense IJCAI may make to such claim or action. Moreover, each author agrees to cooperate in any claim or other action seeking to protect or enforce any right the author has granted to IJCAI in the paper. If any such claim or action fails because of facts that constitute a breach of any of the foregoing warranties, each author agrees to reimburse whomever brings such claim or action for expenses and attorney’s fees incurred therein.

c) In return for these rights, IJCAI hereby grants to each author, and the employers for whom the work was performed, royalty-free permission to:
1. retain all proprietary rights (such as patent rights) other than copyright and the publication rights transferred to IJCAI;
2. personally reuse all or portions of the paper in other works of their own authorship;
3. make oral presentation of the material in any forum;
4. reproduce, or have reproduced, the paper for the author’s personal use, or for company use provided that IJCAI copyright and the source are indicated, and that the copies are not used in a way that implies IJCAI endorsement of a product or service of an employer, and that the copies per se are not offered for sale.
The foregoing right shall not permit the posting of the paper in electronic or digital form on any computer network, except by the author or the author’s employer, and then only on the author’s or the employer’s own World Wide Web page or ftp site. Such Web page or ftp site, in addition to the aforementioned requirements of this Paragraph, must provide an electronic reference or link back to the IJCAI electronic server (http://www.ijcai.org), and shall not post other IJCAI copyrighted materials not of the author’s or the employer’s creation (including tables of contents with links to other papers) without IJCAI’s written permission;
>5. make limited distribution of all or portions of the above paper prior to publication.
6. In the case of work performed under U.S. Government contract, IJCAI grants the U.S. Government royalty-free permission to reproduce all or portions of the above paper, and to authorize others to do so, for U.S. Government purposes.
In the event the above paper is not accepted and published by IJCAI, or is withdrawn by the author(s) before acceptance by IJCAI, this agreement becomes null and void.