@COMMENT This file was generated by bib2html.pl <https://sourceforge.net/projects/bib2html/> version 0.94
@COMMENT written by Patrick Riley <http://sourceforge.net/users/patstg/>
@COMMENT This file came from Kuldeep S. Meel's publication pages at
@COMMENT http://www.comp.nus.edu.sg/~meel/publications/
@inproceedings{PMVB23,
  title={Constraint Optimization over Semirings},
  author={
    Pavan, A. and Meel, Kuldeep S. and Vinodchandran, N. V. and Bhattacharyya,
    Arnab
  },
  month=jan,
  nameorder={random},
  bib2html_dl_pdf={../Papers/aaai23-pmvb.pdf},
  year={2023},
  booktitle=AAAI,
  bib2html_rescat={Misc},
  bib2html_pubtype={Refereed Conference},
  abstract={
    The interpretation of logical formulas over semirings, which provide more
    information than simply the truth or falsity of a statement, have
    applications in computer science fields such as AI, databases, security, and
    logic. These semirings include the Viterbi semiring, the min-max or access
    control semiring, the tropical semiring, and the fuzzy semiring. This work
    explores the complexity of constraint optimization problems over semirings.
    The generic optimization problem studied is: given a propositional formula
    $\varphi$ over $n$ variables and a semiring $(K, +, \cdot, 0, 1)$, find the
    maximum value of all possible interpretations of $\varphi$ over $K$. This
    can be seen as a generalization of the well-known satisfiability problem,
    where a propositional formula is satisfiable if and only if the maximum
    value over all interpretations/assignments over the Boolean semiring is 1. A
    related problem is to find an interpretation that achieves the maximum
    value. This work focuses on these optimization problems over the Viterbi
    semiring, which are called optConfVal and optConf. It is shown that for
    general propositional formulas in negation normal form, optConfVal and
    optConf are in FPNP. When the input formula $\varphi$ is represented in
    conjunctive normal form, the complexity of optConf is investigated. For CNF
    formulae, an upper bound on the value of optConf as a function of the number
    of maximum satisfiable clauses is derived. It is shown that if $r$ is the
    maximum number of satisfiable clauses in a CNF formula with $m$ clauses,
    then its optConf value is at most $\frac{1}{4m-r}$. Based on this result, it
    is established that optConf for CNF formulae is hard for the complexity
    class FPNP[log]. Polynomial-time approximation algorithms are also designed,
    and the inapproximability of optConfVal is established. Similar complexity
    results for these optimization problems over other semirings, such as the
    tropical, fuzzy, and access control semirings, are also established.
  },
  keywords={Misc},
}