Skip to main content

SATISFACTIBILIDAD Y OPTIMIZACION CON CERTIFICADOS DE PRUEBA MAS ALLA DE RESOLUCION

PID2022-138506NB-C22

•
Funding agency name Agencia Estatal de Investigación
Funding agency acronym AEI
Program Programa Estatal para Impulsar la Investigación Científico-Técnica y su Transferencia
Subprogram Subprograma Estatal de Generación de Conocimiento
Call Proyectos de I+D+i (Generación de Conocimiento y Retos Investigación)
Call year 2022
State Plan 2021-2023 Plan Estatal de Investigación Científica y Técnica y de Innovación
Beneficiary centre UNIVERSITAT POLITECNICA DE CATALUNYA

Resultados relacionados

Resultados totales (Incluyendo duplicados): 8
Encontrada(s) 1 página(s)

DIGITAL.CSIC. Repositorio Institucional del CSIC
Publication Artículo científico (JournalArticle)

Polynomial calculus for optimization

  • Bonacina, Ilario
  • Bonet, María Luisa
  • Levy, Jordi
MaxSAT is the problem of finding an assignment satisfying the maximum number of clauses in a CNF formula. We consider a natural generalization of this problem to generic sets of polynomials and propose a weighted version of Polynomial Calculus to address this problem. Weighted Polynomial Calculus is a natural generalization of the systems MaxSAT-Resolution and weighted Resolution. Unlike such systems, weighted Polynomial Calculus manipulates polynomials with coefficients in a finite field and either weights in N or Z. We show the soundness and completeness of weighted Polynomial Calculus via an algorithmic procedure. Weighted Polynomial Calculus, with weights in N and coefficients in F2, is able to prove efficiently that Tseitin formulas on a connected graph are minimally unsatisfiable. Using weights in Z, it also proves efficiently that the Pigeonhole Principle is minimally unsatisfiable., This work was supported by the grant numbers PID2019-109137GB-C21, PID2019-109137GB-C22, IJC2018-035334-I, PID2022-138506NB-C21, and PID2022-138506NB-C22 funded by AEI., Peer reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

Polynomial calculus for optimization

  • Bonacina, Ilario|||0000-0002-5697-8070
  • Bonet Carbonell, M. Luisa|||0000-0003-1646-7177
  • Levy Díaz, Jordi
MaxSAT is the problem of finding an assignment satisfying the maximum number of clauses in a CNF formula. We consider a natural generalization of this problem to generic sets of polynomials and propose a weighted version of Polynomial Calculus to address this problem. Weighted Polynomial Calculus is a natural generalization of the systems MaxSAT-Resolution and weighted Resolution. Unlike such systems, weighted Polynomial Calculus manipulates polynomials with coefficients in a finite field and either weights in ℕ or ℤ. We show the soundness and completeness of weighted Polynomial Calculus via an algorithmic procedure. Weighted Polynomial Calculus, with weights in ℕ and coefficients in F2, is able to prove efficiently that Tseitin formulas on a connected graph are minimally unsatisfiable. Using weights in ℤ, it also proves efficiently that the Pigeonhole Principle is minimally unsatisfiable., This work was supported by the grant numbers PID2019-109137GB-C21, PID2019-109137GB-C22, IJC2018-035334-I, PID2022138506NB-C21, and PID2022-138506NB-C22 funded by AEI. This work was partially done while Maria Luisa Bonet and Jordi Levy were visiting the Simons Institute for the Theory of Computing during the Spring of 2023., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

Maximum linear arrangement: exact algorithms for specific classes of graphs and approximation algorithms for wide classes of graphs

  • Alemany Puig, Lluís|||0000-0002-3874-991X
  • Esteban Ángeles, Juan Luis|||0000-0003-0072-6576
  • Ferrer Cancho, Ramon|||0000-0002-7820-923X
Linear arrangements of graphs are a well-known type of graph labeling and are found in many important computational problems. A linear arrangement is usually defined as a permutation of the n vertices of a graph. An intuitive geometric setting is that of vertices lying on consecutive integer positions in the real line, starting at 1; edges are often drawn as semicircles above the real line. A well-known computational problem is the Minimum Linear Arrangement Problem (minLA) where the goal is to find an arrangement that minimizes the sum of edge lengths. In this paper we study the Maximum Linear Arrangement problem (MaxLA), the counterpart of minLA.We devise a new characterization of maximum arrangements of general graphs, and prove that MaxLA can be solved for k-regular graphs (k ≤ 2) in time O(n), and for k-linear trees (k ≤ 2) in time O(n). We present two constrained variants of MaxLA we call bipartite MaxLA and 1-thistle MaxLA. We prove that the former can be solved in time O(n) for any connected bipartite graph; the latter can be solved by an algorithm that typically runs in time O (n3 log n) on unlabeled trees. We show that bipartite MaxLA is a 3/2-approximation algorithm for MaxLA for trees., Open Access funding provided thanks to the CRUE-CSIC agreement with Springer Nature. The authors’ research is supported by a recognition 2021 SGR-Cat (01266 LQMC) from AGAUR (Generalitat de Catalunya). LAP is supported by Secretaria d’Universitats i Recerca de la Generalitat de Catalunya and the Social European Fund and a Ph.D. contract extension funded by Banco Santander. JLE is supported by grant PID2022-138506NB-C22 funded by Agencia Estatal de Investigación. LAP and RFC are supported by the grant PID2024-155946NB-I00 funded by Ministerio de Ciencia, Innovación y Universidades (MICIU), Agencia Estatal de Investigación (AEI/10.13039/501100011033) and the European Social Fund Plus (ESF+)., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

Consistency of relations over monoids

  • Atserias, Albert|||0000-0002-3732-1989
  • Kolaitis, Phokion
The interplay between local consistency and global consistency has been the object of study in several different areas, including probability theory, relational databases, and quantum information. For relational databases, Beeri, Fagin, Maier, and Yannakakis showed that a database schema is acyclic if and only if it has the local-to-global consistency property for relations, which means that every collection of pairwise consistent relations over the schema is globally consistent. More recently, the same result has been shown under bag semantics. In this paper, we carry out a systematic study of local vs. global consistency for relations over positive commutative monoids, which is a common generalization of ordinary relations and bags. Let K be an arbitrary positive commutative monoid. We begin by showing that acyclicity of the schema is a necessary condition for the local-to-global consistency property for K-relations to hold. Unlike the case of ordinary relations and bags, however, we show that acyclicity is not always sufficient. After this, we characterize the positive commutative monoids for which acyclicity is both necessary and sufficient for the local-to-global consistency property to hold; this characterization involves a combinatorial property of monoids, which we call the transportation property. We then identify several different classes of monoids that possess the transportation property. As our final contribution, we introduce a modified notion of local consistency of K-relations, which we call pairwise consistency up to the free cover. We prove that, for all positive commutative monoids K, even those without the transportation property, acyclicity is both necessary and sufficient for every family of K-relations that is pairwise consistent up to the free cover to be globally consistent., Atserias was partially supported by grant PID2022-138506NB-C22 (PROOFS BEYOND) and the Severo Ochoa and María de Maeztu Program for Centers and Units of Excellence in R&D (CEX2020-001084-M) of the AEI, and the CERCA and ICREA Academia Programmes of the Generalitat de Catalunya. Kolaitis was partially supported by NSF Grant 1814152., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

Consistency witnesses for annotated relations

  • Atserias, Albert|||0000-0002-3732-1989
  • Kolaitis, Phokion
The study of local consistency vs. global consistency of database relations received considerable attention in the early days of relational database theory. In a recent paper, we investigated the notions of local consistency and global consistency for annotated relations, where the annotations come from a positive commutative monoid. One of the differences from the classical case is that the join of two consistent annotated relations need not always be a witness of their consistency. Here, we bring to center stage the notion of a consistency witness function for annotated relations, investigate the properties of consistency witness functions, and provide a new perspective to understanding the interplay between local and global consistency for annotated relations., Atserias was partially supported by grant no. PID2022-138506NB-C22 (PROOFS BEYOND) and the Severo Ochoa and María de Maeztu Program for Centers and Units of Excellence in R&D (CEX2020-001084-M) of the AEI, and the CERCA and ICREA Academia Programmes of the Generalitat., Peer Reviewed
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

Polynomial calculus for optimization

  • Bonacina, Ilario
  • Bonet Carbonell, M. Luisa
  • Levy Díaz, Jordi
MaxSAT is the problem of finding an assignment satisfying the maximum number of clauses in a CNF formula. We consider a natural generalization of this problem to generic sets of polynomials and propose a weighted version of Polynomial Calculus to address this problem. Weighted Polynomial Calculus is a natural generalization of the systems MaxSAT-Resolution and weighted Resolution. Unlike such systems, weighted Polynomial Calculus manipulates polynomials with coefficients in a finite field and either weights in ℕ or ℤ. We show the soundness and completeness of weighted Polynomial Calculus via an algorithmic procedure. Weighted Polynomial Calculus, with weights in ℕ and coefficients in F2, is able to prove efficiently that Tseitin formulas on a connected graph are minimally unsatisfiable. Using weights in ℤ, it also proves efficiently that the Pigeonhole Principle is minimally unsatisfiable., This work was supported by the grant numbers PID2019-109137GB-C21, PID2019-109137GB-C22, IJC2018-035334-I, PID2022138506NB-C21, and PID2022-138506NB-C22 funded by AEI. This work was partially done while Maria Luisa Bonet and Jordi Levy were visiting the Simons Institute for the Theory of Computing during the Spring of 2023., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

Consistency of relations over monoids

  • Atserias, Albert
  • Kolaitis, Phokion
The interplay between local consistency and global consistency has been the object of study in several different areas, including probability theory, relational databases, and quantum information. For relational databases, Beeri, Fagin, Maier, and Yannakakis showed that a database schema is acyclic if and only if it has the local-to-global consistency property for relations, which means that every collection of pairwise consistent relations over the schema is globally consistent. More recently, the same result has been shown under bag semantics. In this paper, we carry out a systematic study of local vs. global consistency for relations over positive commutative monoids, which is a common generalization of ordinary relations and bags. Let K be an arbitrary positive commutative monoid. We begin by showing that acyclicity of the schema is a necessary condition for the local-to-global consistency property for K-relations to hold. Unlike the case of ordinary relations and bags, however, we show that acyclicity is not always sufficient. After this, we characterize the positive commutative monoids for which acyclicity is both necessary and sufficient for the local-to-global consistency property to hold; this characterization involves a combinatorial property of monoids, which we call the transportation property. We then identify several different classes of monoids that possess the transportation property. As our final contribution, we introduce a modified notion of local consistency of K-relations, which we call pairwise consistency up to the free cover. We prove that, for all positive commutative monoids K, even those without the transportation property, acyclicity is both necessary and sufficient for every family of K-relations that is pairwise consistent up to the free cover to be globally consistent., Atserias was partially supported by grant PID2022-138506NB-C22 (PROOFS BEYOND) and the Severo Ochoa and María de Maeztu Program for Centers and Units of Excellence in R&D (CEX2020-001084-M) of the AEI, and the CERCA and ICREA Academia Programmes of the Generalitat de Catalunya. Kolaitis was partially supported by NSF Grant 1814152., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

Consistency witnesses for annotated relations

  • Atserias, Albert
  • Kolaitis, Phokion
The study of local consistency vs. global consistency of database relations received considerable attention in the early days of relational database theory. In a recent paper, we investigated the notions of local consistency and global consistency for annotated relations, where the annotations come from a positive commutative monoid. One of the differences from the classical case is that the join of two consistent annotated relations need not always be a witness of their consistency. Here, we bring to center stage the notion of a consistency witness function for annotated relations, investigate the properties of consistency witness functions, and provide a new perspective to understanding the interplay between local and global consistency for annotated relations., Atserias was partially supported by grant no. PID2022-138506NB-C22 (PROOFS BEYOND) and the Severo Ochoa and María de Maeztu Program for Centers and Units of Excellence in R&D (CEX2020-001084-M) of the AEI, and the CERCA and ICREA Academia Programmes of the Generalitat., Peer Reviewed, Postprint (author's final draft)