Browsing by Author "Romero, Miguel"

Now showing 1 - 2 of 2
  • No Thumbnail Available
    Item
    Pliability and Approximating Max-CSPs
    (2023) Romero, Miguel; Wrochna, Marcin; Zivny, Stanislav
    We identify a sufficient condition, treewidth-pliability, that gives a polynomial-time algorithm for an arbitrarily good approximation of the optimal value in a large class of Max-2-CSPs parameterised by the class of allowed constraint graphs (with arbitrary constraints on an unbounded alphabet). Our result applies more generally to the maximum homomorphism problem between two rational-valued structures.
  • Thumbnail Image
    Item
    Regular Queries on Graph Databases
    (2017) Reutter de la Maza, Juan; Romero, Miguel; Vardi, Moshe Y.