Approximation Algorithms for ROUND-UFP and ROUND-SAP

• URL: http://arxiv.org/abs/2202.03492v1
• Date: Mon, 7 Feb 2022 20:15:15 GMT
• Title: Approximation Algorithms for ROUND-UFP and ROUND-SAP
• Authors: Debajyoti Kar, Arindam Khan, Andreas Wiese
• Abstract summary: We study ROUND-UFP and ROUND-SAP, two generalizations of the classical PACKING problem. In ROUND-UFP, the goal is to find a packing of all rectangles into a minimum number of copies (rounds) of the given path. In ROUND-SAP, the tasks are considered to be rectangles and the goal is to find a non-overlapping packing of these rectangles into a minimum number of rounds.
• Score: 0.06875312133832077
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study ROUND-UFP and ROUND-SAP, two generalizations of the classical BIN PACKING problem that correspond to the unsplittable flow problem on a path (UFP) and the storage allocation problem (SAP), respectively. We are given a path with capacities on its edges and a set of tasks where for each task we are given a demand and a subpath. In ROUND-UFP, the goal is to find a packing of all tasks into a minimum number of copies (rounds) of the given path such that for each copy, the total demand of tasks on any edge does not exceed the capacity of the respective edge. In ROUND-SAP, the tasks are considered to be rectangles and the goal is to find a non-overlapping packing of these rectangles into a minimum number of rounds such that all rectangles lie completely below the capacity profile of the edges. We show that in contrast to BIN PACKING, both the problems do not admit an asymptotic polynomial-time approximation scheme (APTAS), even when all edge capacities are equal. However, for this setting, we obtain asymptotic $(2+\varepsilon)$-approximations for both problems. For the general case, we obtain an $O(\log\log n)$-approximation algorithm and an $O(\log\log\frac{1}{\delta})$-approximation under $(1+\delta)$-resource augmentation for both problems. For the intermediate setting of the no bottleneck assumption (i.e., the maximum task demand is at most the minimum edge capacity), we obtain absolute $12$- and asymptotic $(16+\varepsilon)$-approximation algorithms for ROUND-UFP and ROUND-SAP, respectively.

Related papers

• On the query complexity of sampling from non-log-concave distributions [2.4253233571593547]
  We study the problem of sampling from a $d$-dimensional distribution with density $p(x)propto e-f(x)$, which does not necessarily satisfy good isoperimetric conditions. We show that for a wide range of parameters, sampling is strictly easier than optimization by a super-exponential factor in the dimension $d$.
  arXiv  Detail & Related papers  (2025-02-10T06:54:16Z)
• Differentially Private Bilevel Optimization [4.07926531936425]
  We present differentially private (DPright) algorithms for bilevel optimization. These are the first algorithms for this task that are able to provide any desired empirical setting. Our analysis covers constrained and unstudied problems alike.
  arXiv  Detail & Related papers  (2024-09-29T21:52:38Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  We study the Shortest Path (SSP) problem with a linear mixture transition kernel. An agent repeatedly interacts with a environment and seeks to reach certain goal state while minimizing the cumulative cost. Existing works often assume a strictly positive lower bound of the iteration cost function or an upper bound of the expected length for the optimal policy.
  arXiv  Detail & Related papers  (2024-02-14T07:52:00Z)
• Minimum Width for Deep, Narrow MLP: A Diffeomorphism Approach [3.218087085276242]
  We propose a framework that simplifies finding the minimum width for deep, narrows into determining a purely geometrical function denoted as $w(d_x, d_y)$. We provide an upper bound for the minimum width, given by $namemax (2d_x+1, d_y) + alpha(sigma)$, where $0 leq alpha(sigma) leq 2$ represents a constant depending on the activation function.
  arXiv  Detail & Related papers  (2023-08-30T08:58:23Z)
• Optimal Approximation of Zonoids and Uniform Approximation by Shallow Neural Networks [2.7195102129095003]
  We study the following two related problems. The first is to determine what error an arbitrary zonoid in $mathbbRd+1$ can be approximated in the Hausdorff distance by a sum of $n$ line segments. The second is to determine optimal approximation rates in the uniform norm for shallow ReLU$k$ neural networks on their variation spaces.
  arXiv  Detail & Related papers  (2023-07-28T03:43:17Z)
• Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDP [58.13930707612128]
  This work considers the sample complexity of obtaining an $varepsilon$-optimal policy in an average reward Markov Decision Process (AMDP) We prove an upper bound of $widetilde O(H varepsilon-3 ln frac1delta)$ samples per state-action pair, where $H := sp(h*)$ is the span of bias of any optimal policy, $varepsilon$ is the accuracy and $delta$ is the failure probability.
  arXiv  Detail & Related papers  (2022-12-01T15:57:58Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  We investigate the problem of best identification in discounted linear Markov+Delta Decision in the fixed confidence setting under a generative model. The lower bound as the solution of an intricate non- optimization program can be used as the starting point to devise such algorithms.
  arXiv  Detail & Related papers  (2022-08-11T04:12:50Z)
• Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
  We give a sketching-based iterative algorithm that computes $1+varepsilon$ approximate solutions for the ridge regression problem. We also show that this algorithm can be used to give faster algorithms for kernel ridge regression.
  arXiv  Detail & Related papers  (2022-04-13T22:18:47Z)
• On Subspace Approximation and Subset Selection in Fewer Passes by MCMC Sampling [3.1822873305165618]
  Sampling-based subset selection techniques require adaptive sampling iterations with multiple passes over the data. We propose an MCMC algorithm to reduce the number of passes required by previous subset selection algorithms. Our algorithm picks a subset of size $mathrmpoly(k/epsilon)$ that gives $(1+epsilon)$ approximation to the optimal subspace.
  arXiv  Detail & Related papers  (2021-03-20T06:07:30Z)
• Fully Gap-Dependent Bounds for Multinomial Logit Bandit [5.132017939561661]
  We study the multinomial logit (MNL) bandit problem, where at each time step, the seller offers an assortment of size at most $K$ from a pool of $N$ items. We present (i) an algorithm that identifies the optimal assortment $S*$ within $widetildeO(sum_i = 1N Delta_i-2)$ time steps with high probability, and (ii) an algorithm that incurs $O(sum_i notin S* KDelta_i
  arXiv  Detail & Related papers  (2020-11-19T17:52:12Z)
• Streaming Complexity of SVMs [110.63976030971106]
  We study the space complexity of solving the bias-regularized SVM problem in the streaming model. We show that for both problems, for dimensions of $frac1lambdaepsilon$, one can obtain streaming algorithms with spacely smaller than $frac1lambdaepsilon$.
  arXiv  Detail & Related papers  (2020-07-07T17:10:00Z)
• Fixed-Support Wasserstein Barycenters: Computational Hardness and Fast Algorithm [100.11971836788437]
  We study the fixed-support Wasserstein barycenter problem (FS-WBP) We develop a provably fast textitdeterministic variant of the celebrated iterative Bregman projection (IBP) algorithm, named textscFastIBP.
  arXiv  Detail & Related papers  (2020-02-12T03:40:52Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.