The development of novel platforms and techniques for emerging "Big Data" applications requires the availability of real-life datasets for data-driven experiments, which are however out of reach for academic research in most cases as they are typically proprietary. A possible solution is to use synthesized datasets that reflect patterns of real ones in order to ensure high quality experimental findings. A first step in this direction is to use inverse mining techniques such as inverse frequent itemset mining (IFM) that consists of generating a transactional database satisfying given support constraints on the itemsets in an input set, that are typically the frequent ones. This paper introduces an extension of IFM, called many-sorted IFM, where the schemes for the datasets to be generated are those typical of Big Tables as required in emerging big data applications, e.g., social network analytics.
A reformulation of in terms of frequencies instead of supports has been introduced in @cite_3 @cite_6 with the name @math . The two problems are equivalent and have been shown to be in @math and @math -hard. The basic version of the frequency formulation, called , does not fix the number @math of transaction in a feasible database -- the corresponding decision problem has been proved to be @math -complete. A further variant of the problem has been introduced in @cite_3 @cite_6 with the name @math : all itemsets may occur as transactions in @math at most a fixed number of times ( @math ). This problem is in @math and @math -hard.
@cite_6 @cite_3
2026815944 2007278728
We investigate the minimization of Newton's functional for the problem of the body of minimal resistance with maximal height @math cite butt in the class of convex developable functions defined in a disc. This class is a natural candidate to find a (non-radial) minimizer in accordance with the results of cite lrp2. We prove that the minimizer in this class has a minimal set in the form of a regular polygon with @math sides centered in the disc, and numerical experiments indicate that the natural number @math is a non-decreasing function of @math . The corresponding functions all achieve a lower value of the functional than the optimal radially symmetric function with the same height @math . We consider the @math -Center problem and some generalizations. For @math -Center a set of @math center vertices needs to be found in a graph @math with edge lengths, such that the distance from any vertex of @math to its nearest center is minimized. This problem naturally occurs in transportation networks, and therefore we model the inputs as graphs with bounded highway dimension, as proposed by [SODA 2010]. We show both approximation and fixed-parameter hardness results, and how to overcome them using fixed-parameter approximations, where the two paradigms are combined. In particular, we prove that for any @math computing a @math -approximation is W[2]-hard for parameter @math and NP-hard for graphs with highway dimension @math . The latter does not rule out fixed-parameter @math -approximations for the highway dimension parameter @math , but implies that such an algorithm must have at least doubly exponential running time in @math if it exists, unless the ETH fails. On the positive side, we show how to get below the approximation factor of @math by combining the parameters @math and @math : we develop a fixed-parameter @math -approximation with running time @math . Additionally we prove that, unless P=NP, our techniques cannot be used to compute fixed-parameter @math -approximations for only the parameter @math . We also provide similar fixed-parameter approximations for the weighted @math -Center and @math -Partition problems, which generalize @math -Center. The centralized coded caching scheme is a technique proposed by Maddah-Ali and Niesen as a method to reduce the network burden in peak times in a wireless network system. reformulate the problem as designing a corresponding placement delivery array and propose two new schemes from this perspective. These schemes significantly reduce the rate compared with the uncoded caching schemes. However, to implement these schemes, each file should be cut into @math pieces, where @math grows exponentially with the number of users @math . Such a constraint is obviously infeasible in the practical setting, especially when @math is large. Thus, it is desirable to design caching schemes with constant rate @math (independent of @math ) as well as smaller @math . In this paper, we view the centralized coded caching problem in a hypergraph perspective and show that designing a feasible placement delivery array is equivalent to constructing a linear and (6,3)-free 3-uniform 3-partite hypergraph. Several new results and constructions arise from our novel point of view. First, by using the famous (6,3)-theorem in extremal graph theory, we show that constant rate placement delivery arrays with @math growing linearly with @math do not exist. Second, we present two infinite classes of placement delivery arrays to show that constant rate caching schemes with @math growing sub-exponentially with @math do exist. We consider the k-Center problem and some generalizations. For k-Center a set of kcenter vertices needs to be found in a graph G with edge lengths, such that the distance from any vertex ofi¾?G to its nearest center is minimized. This problem naturally occurs in transportation networks, and therefore we model the inputs as graphs with bounded highway dimension, as proposed by [ICALP 2011]. We show both approximation and fixed-parameter hardness results, and how to overcome them using fixed-parameter approximations. In particular, we prove that for any @math computing a @math -approximation is W[2]-hard for parameter k, and NP-hard for graphs with highway dimension @math . The latter does not rule out fixed-parameter @math -approximations for the highway dimension parameteri¾?h, but implies that such an algorithm must have at least doubly exponential running time in h if it exists, unless the ETH fails. On the positive side, we show how to get below the approximation factor ofi¾?2 by combining the parameters k andi¾?h: we develop a fixed-parameter 3 2-approximation with running time @math . We also provide similar fixed-parameter approximations for the weightedk-Center and @math -Partition problems, which generalize k-Center.