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

Packing problems are an important class of optimization problems. Theprobably most well-known problem if this type is knapsack and manygeneralizations of it have been studied in the literature like Two-dimensionalGeometric Knapsack (2DKP) and Unsplittable Flow on a Path (UFP). For the lattertwo problems, recently the first polynomial time approximation algorithms withbetter approximation ratios than 2 were presented [G\'alvez et al., FOCS2017][Grandoni et al., STOC 2018].  In this paper we break the barrier of 2 for the Storage Allocation Problem(SAP) which is a natural intermediate problem between 2DKP and UFP. We aregiven a path with capacitated edges and a set of tasks where each task has astart vertex, an end vertex, a size, and a profit. We seek to select the mostprofitable set of tasks that we can draw as non-overlapping rectanglesunderneath the capacity profile of the edges where the height of each rectangleequals the size of the corresponding task.  This problem is motivated by settings of allocation resources like memory,bandwidths, etc. where each request needs a contiguous portion of the resource.The best known polynomial time approximation algorithm for SAP has anapproximation ratio of 2+epsilon$ [M\"omke and Wiese, ICALP 2015] and no betterquasi-polynomial time algorithm is known. We present a polynomial time (63/32)< 1.969-approximation algorithm for the case of uniform edge capacities and aquasi-polynomial time (1.997)-approximation algorithm for non-uniformquasi-polynomially bounded edge capacities. Finally, we show that under slightresource augmentation we can obtain approximation ratios of 3/2 + epsilon inpolynomial time and 1 + epsilon in quasi-polynomial time, both for arbitraryedge capacities.

Breaking the Barrier of 2 for the Storage Allocation Problem