203 research outputs found
Non-Linear Paging
No full textWe formulate and study non-linear paging - a broad model of online paging where the size of subsets of pages is determined by a monotone non-linear set function of the pages. This model captures the well-studied classic weighted paging and generalized paging problems, and also submodular and supermodular paging, studied here for the first time, that have a range of applications from virtual memory to machine learning.
Unlike classic paging, the cache threshold parameter k does not yield good competitive ratios for non-linear paging. Instead, we introduce a novel parameter that generalizes the notion of cache size to the non-linear setting. We obtain a tight deterministic -competitive algorithm for general non-linear paging and a o(log²)-competitive lower bound for randomized algorithms. Our algorithm is based on a new generic LP for the problem that captures both submodular and supermodular paging, in contrast to LPs used for submodular cover settings. We finally focus on the supermodular paging problem, which is a variant of online set cover and online submodular cover, where sets are repeatedly requested to be removed from the cover. We obtain polylogarithmic lower and upper bounds and an offline approximation algorithm
An EPTAS for Budgeted Matching and Budgeted Matroid Intersection via Representative Sets
No full textWe study the budgeted versions of the well known matching and matroid intersection problems. While both problems admit a polynomial-time approximation scheme (PTAS) [Berger et al. (Math. Programming, 2011), Chekuri, Vondrák and Zenklusen (SODA 2011)], it has been an intriguing open question whether these problems admit a fully PTAS (FPTAS), or even an efficient PTAS (EPTAS).
In this paper we answer the second part of this question affirmatively, by presenting an EPTAS for budgeted matching and budgeted matroid intersection. A main component of our scheme is a construction of representative sets for desired solutions, whose cardinality depends only on ε, the accuracy parameter. Thus, enumerating over solutions within a representative set leads to an EPTAS. This crucially distinguishes our algorithms from previous approaches, which rely on exhaustive enumeration over the solution set
Unsplittable Flow on a Short Path
No full textIn the Unsplittable Flow on a Path problem (UFP), we are given a path graph with edge capacities and a collection of tasks. Each task is characterized by a demand, a profit, and a subpath. Our goal is to select a maximum profit subset of tasks such that the total demand of the selected tasks that use each edge e is at most the capacity of e. BagUFP is the generalization of UFP where tasks are partitioned into bags, and we are allowed to select at most one task per bag. UFP admits a PTAS [Grandoni,Mömke,Wiese'22] but not an EPTAS [Wiese'17]. BagUFP is APX-hard [Spieksma'99] and the current best approximation is O(log n/log log n) [Grandoni,Ingala,Uniyal'15], where n is the number of tasks.
In this paper, we study the mentioned two problems when parameterized by the number m of edges in the graph, with the goal of designing faster parameterized approximation algorithms. We present a parameterized EPTAS for BagUFP, and a substantially faster parameterized EPTAS for UFP (which is an FPTAS for m = O(1)). We also show that a parameterized FPTAS for UFP (hence for BagUFP) does not exist, therefore our results are qualitatively tight
Lower Bounds for Matroid Optimization Problems with a Linear Constraint
No full textWe study a family of matroid optimization problems with a linear constraint (MOL). In these problems, we seek a subset of elements which optimizes (i.e., maximizes or minimizes) a linear objective function subject to (i) a matroid independent set, or a matroid basis constraint, (ii) additional linear constraint. A notable member in this family is budgeted matroid independent set (BM), which can be viewed as classic 0/1-Knapsack with a matroid constraint. While special cases of BM, such as knapsack with cardinality constraint and multiple-choice knapsack, admit a fully polynomial-time approximation scheme (Fully PTAS), the best known result for BM on a general matroid is an Efficient PTAS. Prior to this work, the existence of a Fully PTAS for BM, and more generally, for any problem in the family of MOL problems, has been open.
In this paper, we answer this question negatively by showing that none of the (non-trivial) problems in this family admits a Fully PTAS. This resolves the complexity status of several well studied problems. Our main result is obtained by showing first that exact weight matroid basis (EMB) does not admit a pseudo-polynomial time algorithm. This distinguishes EMB from the special cases of k-subset sum and EMB on a linear matroid, which are solvable in pseudo-polynomial time. We then obtain unconditional hardness results for the family of MOL problems in the oracle model (even if randomization is allowed), and show that the same results hold when the matroids are encoded as part of the input, assuming P ≠ NP. For the hardness proof of EMB, we introduce the Π-matroid family. This intricate subclass of matroids, which exploits the interaction between a weight function and the matroid constraint, may find use in tackling other matroid optimization problems
An AFPTAS for Bin Packing with Partition Matroid via a New Method for LP Rounding
No full textWe consider the Bin Packing problem with a partition matroid constraint. The input is a set of items of sizes in [0,1], and a partition matroid over the items. The goal is to pack the items in a minimum number of unit-size bins, such that each bin forms an independent set in the matroid. This variant of classic Bin Packing has natural applications in secure storage on the Cloud, as well as in equitable scheduling and clustering with fairness constraints.
Our main result is an asymptotic fully polynomial-time approximation scheme (AFPTAS) for Bin Packing with a partition matroid constraint. This scheme generalizes the known AFPTAS for Bin Packing with Cardinality Constraints and improves the existing asymptotic polynomial-time approximation scheme (APTAS) for Group Bin Packing, which are both special cases of Bin Packing with partition matroid. We derive the scheme via a new method for rounding a (fractional) solution for a configuration-LP. Our method uses this solution to obtain prototypes, in which items are interpreted as placeholders for other items, and applies fractional grouping to modify a fractional solution (prototype) into one having desired integrality properties
Budgeted Matroid Maximization: a Parameterized Viewpoint
No full textWe study budgeted variants of well known maximization problems with multiple matroid constraints. Given an -matchoid ℳ on a ground set E, a profit function p:E → ℝ_{≥ 0}, a cost function c:E → ℝ_{≥ 0}, and a budget B ∈ ℝ_{≥ 0}, the goal is to find in the -matchoid a feasible set S of maximum profit p(S) subject to the budget constraint, i.e., c(S) ≤ B. The budgeted -matchoid (BM) problem includes as special cases budgeted -dimensional matching and budgeted -matroid intersection. A strong motivation for studying BM from parameterized viewpoint comes from the APX-hardness of unbudgeted -dimensional matching (i.e., B = ∞) already for = 3. Nevertheless, while there are known FPT algorithms for the unbudgeted variants of the above problems, the budgeted variants are studied here for the first time through the lens of parameterized complexity.
We show that BM parametrized by solution size is W[1]-hard, already with a degenerate single matroid constraint. Thus, an exact parameterized algorithm is unlikely to exist, motivating the study of FPT-approximation schemes (FPAS). Our main result is an FPAS for BM (implying an FPAS for -dimensional matching and budgeted -matroid intersection), relying on the notion of representative set - a small cardinality subset of elements which preserves the optimum up to a small factor. We also give a lower bound on the minimum possible size of a representative set which can be computed in polynomial time
An EPTAS for Cardinality Constrained Multiple Knapsack via Iterative Randomized Rounding
No full textIn [Math. Oper. Res., 2011], Fleischer et al. introduced a powerful technique for solving the generic class of separable assignment problems (SAP), in which a set of items of given values and weights needs to be packed into a set of bins subject to separable assignment constraints, so as to maximize the total value. The approach of Fleischer at al. relies on solving a configuration LP and sampling a configuration for each bin independently based on the LP solution. While there is a SAP variant for which this approach yields the best possible approximation ratio, for various special cases, there are discrepancies between the approximation ratios obtained using the above approach and the state-of-the-art approximations. This raises the following natural question: Can we do better by iteratively solving the configuration LP and sampling a few bins at a time?
To assess the potential of the iterative approach we consider a specific SAP variant as a case-study, Uniform Cardinality Constrained Multiple Knapsack, for which we answer this question affirmatively. The input is a set of items, each has a value and a weight, and a set of uniform capacity bins. The goal is to assign a subset of the items of maximum total value to the bins such that (i) the capacity of any bin is not exceeded, and (ii) the number of items assigned to each bin satisfies a given cardinality constraint. While the technique of Fleischer et al. yields a (1-1/e)-approximation for the problem, we show that iterative randomized rounding leads to efficient polynomial time approximation scheme (EPTAS), thus essentially resolving the complexity status of the problem. Our analysis of iterative randomized rounding may be useful for solving other SAP variants
Groups containing a CC-subgroup
No full textGemeinsame Resultate mit Zvi Arad (Bar Ilan U + Academic College Netanya)Joint results with Zvi Arad that had appeared in Comm.Alg. and J.of Lie Theor
Dead Sea Asphalt from the Excavations in Tel Arad and small Tel Malhata
No full textAsphalt was found in the excavations of Tel Arad and Small Tel Malhata in the Northern Negev, Israel, in levels dated as Early Bronze I and II. Detailed chemical analysis indicates that this material, used as a glue on various utensils, resembles natural occurrences of asphalt blocks which are occasionally found floating on the Dead Sea. Although the historical records of 2000 years ago indicate that Dead Sea asphalt has been an important trade item of the region, this is the first evidence that Dead Sea material can be found outside its source area. It also indicates that the export of Dead Sea asphalt had begun at least 3000 years before the earliest historical record by Diodorus of Sicily (ca. 50 A.D.).Du bitume a été trouvé au cours de fouilles de Tell Arad et du petit Tell Malhata dans le nord du Néguev, en Israël, dans les niveaux datés du Bronze Ancien I et II. L'analyse chimique indique que ce bitume, utilisé sur des objets divers, est de même nature que les blocs de bitume que l'on trouve parfois flottant à la surface de la Mer Morte. Les textes anciens mentionnent que le bitume de la Mer Morte était une denrée d'exportation importante de la région il y a deux mille ans; le bitume de Tell Arad et du petit Tell Malhata est le premier témoin de ce matériau en dehors de son lieu d'origine. Il indique aussi que le commerce du bitume de la Mer Morte a commencé au moins 3000 ans avant l'apparition de la première mention historique faite par Diodore de Sicile vers l'an 50 de notre ère.Nissenbaum Arie, Serban Andrei, Amiran Ruth, Ilan Ornit. Dead Sea Asphalt from the Excavations in Tel Arad and small Tel Malhata. In: Paléorient, 1984, vol. 10, n°1. pp. 157-161
VITICULTURE OF MINIS – MĂDERAT VINEYARD, HISTORY AND ACCOMPLISHMENTS - METHODOLOGICAL ISSUES –
No full textThe author presents the history of vine culture and wine production in Arad County Vineyards, MiniÈ™ - Măderat area, focusing on the deseases of vine plantations along the way. In the end, the author shows some methodological aspects which increase the efficiency of content teaching by seminar activities with the students of „Aurel Vlaicu†University of Arad, Food Engineering, Tourism and Environement Protection Faculty.Â
- …
