English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

A property $\Pi$ on a finite set $U$ is \emph{monotone} if for every $X\subseteq U$ satisfying $\Pi$, every superset $Y \subseteq U$ of $X$ alsosatisfies $\Pi$. Many combinatorial properties can be seen as monotoneproperties. The problem of finding a minimum subset of $U$ satisfying $\Pi$ isa central problem in combinatorial optimization. Although manyapproximate/exact algorithms have been developed to solve this kind of problemon numerous properties, a solution obtained by these algorithms is oftenunsuitable for real-world applications due to the difficulty of buildingaccurate mathematical models on real-world problems. A promising approach toovercome this difficulty is to \emph{enumerate} multiple small solutions ratherthan to \emph{find} a single small solution. To this end, given a weightfunction $w: U \to \mathbb N$ and an integer $k$, we devise algorithms that\emph{approximately} enumerate all minimal subsets of $U$ with weight at most$k$ satisfying $\Pi$ for various monotone properties $\Pi$, where "approximateenumeration" means that algorithms output all minimal subsets satisfying $\Pi$whose weight at most $k$ and may output some minimal subsets satisfying $\Pi$whose weight exceeds $k$ but is at most $ck$ for some constant $c \ge 1$. Thesealgorithms allow us to efficiently enumerate minimal vertex covers, minimaldominating sets in bounded degree graphs, minimal feedback vertex sets, minimalhitting sets in bounded rank hypergraphs, etc., of weight at most $k$ withconstant approximation factors.

Efficient Constant-Factor Approximate Enumeration of Minimal Subsets for Monotone Properties with Weight Constraints