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/

Zendy Plus

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

Zendy Tools

Zendy Open

A significant progress has been made in the past three decades over the studyof combinatorial NP optimization problems and their associated optimization andapproximate classes, such as NPO, PO, APX (or APXP), and PTAS. Unfortunately, acollection of problems that are simply placed inside the P-solvableoptimization class PO never have been studiously analyzed regarding their exactcomputational complexity. To improve this situation, the existing frameworkbased on polynomial-time computability needs to be expanded and further refinedfor an insightful analysis of various approximation algorithms targetingoptimization problems within PO. In particular, we deal with those problemscharacterized in terms of logarithmic-space computations and uniform-circuitcomputations. We are focused on nondeterministic logarithmic-space (NL)optimization problems or NPO problems. Our study covers a wide range ofoptimization and approximation classes, dubbed as, NLO, LO, APXL, and LSAS aswell as new classes NC1O, APXNC1, NC1AS, and AC0O, which are founded on uniformfamilies of Boolean circuits. Although many NL decision problems can benaturally converted into NL optimization (NLO) problems, few NLO problems havebeen studied vigorously. We thus provide a number of new NLO problems fallinginto those low-complexity classes. With the help of NC1 or AC0approximation-preserving reductions, we also identify the most difficultproblems (known as complete problems) inside those classes. Finally, wedemonstrate a number of collapses and separations among those refinedoptimization and approximation classes with or without unprovencomplexity-theoretical assumptions.

Uniform-Circuit and Logarithmic-Space Approximations of Refined Combinatorial Optimization Problems