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 Tools annual

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 Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

In the classical Maximum Acyclic Subgraph problem (MAS), given adirected-edge weighted graph, we are required to find an ordering of the nodesthat maximizes the total weight of forward-directed edges. MAS admits a 2approximation, and this approximation is optimal under the Unique GameConjecture.  In this paper we consider a generalization of MAS, the Restricted MaximumAcyclic Subgraph problem (RMAS), where each node is associated with a list ofinteger labels, and we have to find a labeling of the nodes so as to maximizethe weight of edges whose head label is larger than the tail label. The bestknown (almost trivial) approximation for RMAS is 4.  The interest of RMAS is mostly due to its connections with the Vertex Pricingproblem (VP). In VP we are given an undirected graph with positive edgebudgets. A feasible solution consists of an assignment of non-negative pricesto the nodes. The profit for each edge $e$ is the sum of its endpoints pricesif that sum is at most the budget of $e$, and zero otherwise. Our goal is tomaximize the total profit. The best known approximation for VP, which worksanalogously to the mentioned approximation algorithm for RMAS, is 4. Improvingon that is a challenging open problem. On the other hand, the best known 2inapproximability result is due to a reduction from a special case of RMAS.  In this paper we present an improved LP-rounding $2\sqrt{2}$ approximationfor RMAS. Our result shows that, in order to prove a 4 hardness ofapproximation result for VP (if possible), one should consider reductions fromharder problems. Alternatively, our approach might suggest a different way todesign approximation algorithms for VP.

An LP-Rounding $2\sqrt{2}$ Approximation for Restricted Maximum Acyclic Subgraph