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

We revisit various PTAS's (Polynomial Time Approximation Schemes) forminimization versions of dense problems, and show that they can be performedwith sublinear query complexity. This means that not only do we obtain a(1+eps)-approximation to the NP-Hard problems in polynomial time, but alsoavoid reading the entire input. This setting is particularly advantageous whenthe price of reading parts of the input is high, as is the case, for examples,where humans provide the input. Trading off query complexity with approximationis the raison d'etre of the field of learning theory, and of the ERM (EmpiricalRisk Minimization) setting in particular. A typical ERM result, however, doesnot deal with computational complexity. We discuss two particular problems forwhich (a) it has already been shown that sublinear querying is sufficient forobtaining a (1 + eps)-approximation using unlimited computational power (an ERMresult), and (b) with full access to input, we could get a(1+eps)-approximation in polynomial time (a PTAS). Here we show that neitherbenefit need be sacrificed. We get a PTAS with efficient query complexity.

A note on: No need to choose: How to get both a PTAS and Sublinear Query Complexity