Search

An incidence of a graph G is a vertex-edge pair (v , e) such that the vertex v is incident with the edge e. A proper incidence k-coloring of a graph is a coloring of its incidences involving k colors so that two incidences (u , e) and (w , f) receive distinct colors if and only if u = w , or e = f , or u w ∈ { e , f }. In this paper, we present some idea of using the incidence coloring to model a kind of multi-frequency assignment problem , in which each transceiver can be simultaneously in both sending and receiving modes, and then establish some theoretical and algorithmic aspects of the incidence coloring. Specifically, we conjecture that if G is the Mycielskian of some graph then it has a proper incidence (Δ (G) + 2) -coloring. Actually, our conjecture is motivated by the " (Δ + 2) conjecture" of Brualdi and Quinn Massey in 1993, which states that every graph G has a proper incidence (Δ (G) + 2) -coloring, and was disproved in 1997 by Guiduli, who pointed out that the Paley graphs with large maximum degree are counterexamples (yet they are all known counterexamples to the " (Δ + 2) conjecture", and are not Mycielskians of any graph). To support our conjecture, we prove in this paper that if G is the Mycielskian of a graph H with | H | ≥ 3 Δ (H) + 2 , then we can construct a proper incidence (Δ (G) + 1) -coloring of G in cubic time, and if G is the Mycielskian of an incidence (Δ (H) + 1) -colorable graph H with | H | ≤ 2 Δ (H) , or the Mycielskian of an incidence (Δ (H) + 2) -colorable graph H with | H | ≥ 2 Δ (H) + 1 , then G has a proper incidence (Δ (G) + 2) -coloring. The minimum positive integer k such that the Mycielskian of a cycle or a path has a proper incidence k -coloring is also determined. [ABSTRACT FROM AUTHOR]

The Maximum Weight Independent Set (MWIS) problem on finite undirected graphs with vertex weights asks for a set of pairwise nonadjacent vertices of maximum weight sum. MWIS is one of the most investigated and most important algorithmic graph problems; it is well known to be NP-complete, and it remains NP-complete even under various strong restrictions such as for triangle-free graphs. Its complexity for P k -free graphs, k ≥ 7 , is an open problem. In [7] , it is shown that MWIS can be solved in polynomial time for (P 7 ,triangle)-free graphs. This result is extended by Maffray and Pastor [22] showing that MWIS can be solved in polynomial time for (P 7 ,bull)-free graphs. In the same paper, they also showed that MWIS can be solved in polynomial time for (S 1 , 2 , 3 ,bull)-free graphs. In this paper, using a similar approach as in [7] , we show that MWIS can be solved in polynomial time for (S 1 , 2 , 4 ,triangle)-free graphs which generalizes the result for (P 7 ,triangle)-free graphs. [ABSTRACT FROM AUTHOR]

This paper concerns the behavior of an SINR diagram of wireless systems, composed of a set S of n stations embedded in R d , when restricted to the corresponding Voronoi diagram imposed on S. The diagram obtained by restricting the SINR zones to their corresponding Voronoi cells is referred to hereafter as an SINR + Voronoi diagram. Uniform SINR diagrams, where all stations transmit with the same power, are simple and nicely structured, e.g., the station reception zones are convex and "fat". In contrast, nonuniform SINR diagrams might be complex; the reception zones might be fractured and their boundaries might contain many singular points. In this paper, we establish the perhaps surprising fact that a nonuniform SINR+Voronoi diagram is topologically almost as nice as a uniform SINR diagram. In particular, it is convex and effectively5 fat. This holds for every power assignment, every path-loss parameter α and every dimension d ≥ 1. The convexity property also holds for every SINR threshold β > 0 , and the effective fatness property holds for any β > 1. These fundamental properties provide a theoretical justification to engineering practices basing zonal tessellations on the Voronoi diagram, and help to explain the soundness and efficacy of such practices. We also consider two algorithmic applications. The first concerns the Power Control with Voronoi Diagram (PCVD) problem, where given n stations embedded in some polygon P , it is required to find the power assignment that optimizes the SINR threshold of the transmission station s i for any given reception point p ∈ P in its Voronoi cell ▪. The second application is approximate point location; we show that for SINR+Voronoi zones, this task can be solved considerably more efficiently than in the general non-uniform case. [ABSTRACT FROM AUTHOR]

In this paper, we introduce a new graph structure named an ST -reachable directed acyclic graph which is a directed acyclic graph (DAG) that guarantees reachability (i.e., a directed path exists) from every sender to every target. When an arbitrarily connected undirected graph G = (V , E) and two sets of the vertices, senders S (⊂ V) and targets T (⊂ V), are given, we consider the construction of a minimal ST -reachable DAG by changing some undirected edges to arcs and removing the remaining edges. In this paper, we present the necessary and sufficient condition under which a minimal ST -reachable DAG can be constructed when | S | ≤ 2 and | T | ≤ 2 , and propose a self-stabilizing algorithm for constructing a minimal ST -reachable DAG (if it exists) when an arbitrarily connected undirected graph, S (| S | ≤ 2) and T (| T | ≤ 2) are given. Moreover, our proposed algorithm can detect the non-existence of any ST -reachable DAG if the ST -reachable DAG of the given graph and two sets of vertices, S and T , do not exist. [ABSTRACT FROM AUTHOR]

• In this paper, we consider the submodular edge cover problem with submodular penalties. • We give a 2Δ-approximation algorithm for the above problem, where Δ is the maximal degree of the graph G. • We transform the submodular edge cover problem into a submodular set cover problem and show that there exists a Δ + 1 -approximation algorithm. In this paper, we consider the submodular edge cover problem with submodular penalties. In this problem, we are given an undirected graph G = (V , E) with vertex set V and edge set E. Assume the covering cost function c : 2 E → R + and the penalty function p : 2 V → R + are both submodular with p non-decreasing, c (∅) = 0 and p (∅) = 0. The goal of the submodular edge cover problem with submodular penalties is to select an edge subset to cover some vertices and penalize the vertex subset containing uncovered vertices such that the total cost of covering and penalty is minimized. For this problem, we first give a 2Δ-approximation algorithm by using a primal-dual technique, where Δ is the maximal degree of the graph G. Then we transform this problem into a submodular set cover problem, and by applying a known result for the submodular set cover problem we conclude that there is an approximation algorithm with an approximation ratio Δ + 1. [ABSTRACT FROM AUTHOR]

The problem of partitioning a large complex network equitably into sparse modules with given rules can be modeled by the equitable list d -degenerate coloring of graphs. This paper establishes theoretical results on such a coloring based on a newly proposed conjecture which states that every graph G is equitably d -degenerate k -colorable and equitably d -degenerate k -choosable for every integer k ≥ (Δ (G) + 1) / (d + 1). This conjecture is strong as it implies the Hajnal-Szemerédi theorem on equitable coloring, the equitable list coloring conjecture (Kostochka, Pelsmajer, and West, 2003), the equitable vertex arboricity conjecture (Wu, Zhang, and Li, 2013), and the equitable list vertex arboricity conjecture (Zhang, 2016). In this paper, we confirm this unified conjecture for globally coupled networks, (d + 1) -degenerate graphs, graphs with bounded maximum average degree, and planar graphs with large maximum degree. The equitable d -degenerate k -colorability part of this conjecture is also verified for interval graphs, generalizing a result of Niu, Li, and Zhang (2021). [ABSTRACT FROM AUTHOR]

We are interested in regular expressions that represent word relations in an alphabet-invariant way—for example, the set of all word pairs (u , v) where v is a prefix of u independently of what the alphabet is. Current software systems of formal language objects do not have a mechanism to define such objects. Labelled graphs (transducers and automata) with alphabet-invariant and user-defined labels were considered in a recent paper. In this paper we study derivatives of regular expressions over labels (atomic objects) in some set B. These labels can be any strings as long as the strings represent subsets of a certain monoid. We show that the number of partial derivatives of any type B regular expression is linearly bounded, and that one can define partial derivative labelled graphs, whose transition labels can be elements of another label set X as long as X and B refer to the same monoid. We also show how to use derivatives directly to decide whether a given word is in the language of a regular expression over set specs. Set specs and pairing specs are label sets allowing one to express languages and relations over large alphabets in a natural and concise way such that many algorithms work directly on these labels without the need to expand these labels to linear or quadratic size expressions. [ABSTRACT FROM AUTHOR]

Modern distributed systems are becoming pervasive and increasingly provided with adaptation, (self-)reconfiguration and mobility capability. On one side, to face the challenges of the highly dynamic environments where they are deployed. On the other side, to keep production/maintenance costs down. Therein lies the increasing demand for formal models encompassing all of these aspects (besides concurrency). Hardly any of the classical formalisms like Petri Nets, Automata, and Process Algebra, even though powerful, permits designers to easily specify dynamic structural changes to systems and evaluate their impact on system behaviour. That has led to several extensions of classical formal models (e.g., the Pi calculus or the Nets-within-Nets paradigm) rarely accompanied by suitable analysis techniques. A recent formalization of a class of Rewritable Place-Transition Nets (RwPT) in Maude has proved potentially convenient to specify dynamically reconfigurable systems. Concerning analogous proposals, the RwPT formalism provides more abstraction/flexibility in modelling and efficiency in analysis. Nevertheless, its ability to scale the size of distributed systems built of several similar (nested) components is limited. This paper presents a compositional approach to define large RwPT models in a typical algebraic way and to exploit the modular structure of models during the analysis: Symmetries are implicitly captured by composite node-labelling (reflecting the model's hierarchical structure) that is preserved by net rewrites. A distributed, gracefully degrading production system is used as a case study. Experimental evidence points out the dramatic impact of the approach against a non-modular one and the advantages over alternative techniques. Even if the emphasis is on state-space-based verification, the paper shows the convenience of combining it with structural analysis, which is typical of Petri nets as well. For that purpose, rewrite-rule abstractions are given in the form of guidelines. [ABSTRACT FROM AUTHOR]

There are many infinite families of 2-designs and 3-designs supported by linear codes in the literature. Recently, several infinite families of 4-designs from linear codes were discovered. But no infinite family of linear codes supporting an infinite family of nontrivial simple 5-designs is reported in the literature. It is not easy to construct 5-designs from sporadic codes. Only a small number of sporadic 5-designs supported by linear codes are available in the literature. In this paper, we construct eight 5-designs from some lifted codes of some known linear codes. • There are many infinite families of 2-designs and 3-designs supported by linear codes in the literature. • Recently, several infinite families of 4-designs from linear codes were discovered. • But no infinite family of linear codes supporting an infinite family of nontrivial simple 5-designs is reported in the literature. • It is not easy to construct 5-designs from sporadic codes. Only a small number of sporadic 5-designs supported by linear codes are available in the literature. • In this paper, we construct eight new 5-designs from some lifted codes of some known linear codes. [ABSTRACT FROM AUTHOR]

Sorting is a fundamental component in many different applications including web indexing engines, geographic information systems, data mining and database systems. However, the existing optimal algorithms still cause huge costs when the input data becomes very large. Thus, the approximate sorting for big data is considered in this paper. The goal of approximate sorting for big data is to generate an approximate sorted result, but using less CPU and I/O cost. For big data, we consider the approximate sorting and applications for approximate sorted results in I/O model. The quality of approximate sorting results is usually measured by the distance metrics on permutation space. However, the existing metrics on permutation space are not available for external approximate sorting algorithms. Thus, we propose a new kind of metric named External metric, which ignores the errors and dislocations that happened in each I/O block. The External metric of Spearman's footrule metric is named as External Spearman's footrule metric (short as ESP metric), which is analyzed in this paper. Furthermore, to facilitate a better evaluation of the approximate sorted result, we propose a new metric, named as errors , which directly states the number of dislocation of the elements. The External errors are also considered in this paper. Then, according to the rate-distortion relationship under these two metrics, the lower bound of these two metrics on external approximate sorting problem with t I/O operations is proved. We propose a k-passes external approximate sorting algorithm, named as EASORT, and prove that EASORT is asymptotically optimal under ESP metric. Finally, we consider the applications on approximate sorting results. An index for the approximate sorted result is proposed. The single and range query on approximate sorted result using this index are also analyzed. Further, the sort-merge join on two relations, where one of the relations is approximate sorted or both relations are approximate sorted, are all discussed in this paper. • This paper first discusses the approximate sorting in I/O model. • This paper proposes a new external metric to evaluate the approximate sorted result. • This paper analyzes the lower bound of two metrics of approximate sorted result. • This paper proposes a new external approximate sorting algorithm. • This paper analyzes the applications on approximate sorted result. [ABSTRACT FROM AUTHOR]

Syntactic models constitute one of the main areas of mathematical studies on picture array generation. A number of 2D grammar models have been proposed with motivation from a variety of applications. Parallel Contextual Array Insertion Deletion Grammar (PCAIDG) and Pure 2D Context-Free Grammar (P2DCFG) are two such 2D grammars. In the case of P2DCFG, two new variants are studied with interesting properties. In this paper we show that PCAIDG has higher generative power than the generative powers of two variants of P2DCFG. Further, P systems associated with the grammars PCAIDG, P2DCFG and their variants are considered in the literature. In this paper, we show that the generative power of Parallel Contextual Array Insertion Deletion P System (PCAIDPS) is greater than the generative power of the P system associated with a variant of P2DCFG. [ABSTRACT FROM AUTHOR]

• The approximability and the computational complexity of the Maximum Happy Set problem (MaxHS) are studied. • A (2 Δ + 1) -approximation algorithm for MaxHS on graphs with maximum degree Δ is presented. • The approximation ratio is improved to Δ if the maximum degree Δ is a constant. • The polynomial-time solvability of MaxHS on block/interval graphs is proved. • The NP-hardness of MaxHS on bipartite/cubic graphs is proved. In this paper we study the approximability of the Maximum Happy Set problem (MaxHS) and the computational complexity of MaxHS on graph classes: For an undirected graph G = (V , E) and a subset S ⊆ V of vertices, a vertex v is happy if v and all its neighbors are in S ; otherwise unhappy. Given an undirected graph G = (V , E) and an integer k , the goal of MaxHS is to find a subset S ⊆ V of k vertices such that the number of happy vertices is maximized. MaxHS is known to be NP-hard. In this paper, we design a (2 Δ + 1) -approximation algorithm for MaxHS on graphs with maximum degree Δ. Next, we show that the approximation ratio can be improved to Δ if the maximum degree Δ of the input graph is a constant. Then, we show that MaxHS can be solved in polynomial time if the input graph is restricted to block graphs, or interval graphs. We prove nevertheless that MaxHS on bipartite graphs or on cubic graphs remains NP-hard. [ABSTRACT FROM AUTHOR]

In this paper, we revisit the r -gathering problem. Given sets C and F of points on the plane and distance d (c , f) for each c ∈ C and f ∈ F , an r -gathering of C to F is an assignment A of C to open facilities F ′ ⊆ F such that r or more members of C are assigned to each open facility. The cost of an r -gathering is max c ∈ C ⁡ d (c , A (c)). The r -gathering problem computes the r -gathering minimizing the cost. In this paper we study the r -gathering problem when C and F are on a line and present a O (| C | + | F |) -time algorithm to solve the problem. Our solution is optimal since any algorithm needs to read C and F at least once. [ABSTRACT FROM AUTHOR]

• Several important parameterization methods for completeness reasoning problem are identified. • The completeness reasoning problems parameterized by the sizes of the completeness statements are shown to be para-NP-complete. • For special cases defined by limiting query structures, the parameterized completeness reasoning problems are shown to be intractable. • With data completeness statements of constant size, tractable cases of the parameterized completeness reasoning problem are found. Incompleteness management has become a popular research topic and been viewed in many applications in the area of data quality and data management. Traditional methods for handling incompleteness assume data is totally complete or incomplete. However, in practical applications, data is often partial complete , which means that data is not totally complete but some special parts of the data satisfying given semantic specifications are complete. Intuitively, partial complete data can still give complete answers for queries consistent with the semantic specifications. Therefore, it is highly needed to study the fundamental problems for managing partial complete data. However, as far as known by us, there are only few works focusing on this area. The most important and fundamental problem, completeness reasoning , is studied from the aspect of parameterized complexity by this paper. The completeness reasoning problem, TC-QC (Table Completeness to Query Completeness), is first formally defined and studied by Razniewski et al. [1]. Given completeness statements of data, the goal of the TC-QC problem is to determine whether the result of a special query Q is complete, that is to reason query completeness based on given data completeness. Razniewski et al. have shown that the TC-QC problem is NP- hard even for conjunctive queries , and a natural and interesting question is whether or not TC-QC can be solved efficiently by parameterized algorithms. To answer that, the parameterized complexities of completeness reasoning for conjunctive queries are studied by the paper. First, it is shown that, considering the parameterizations defined by the size of query completeness or table completeness, the parameterized TC-QC problem for conjunctive queries is para-NP- complete , which strongly indicate that the TC-QC problems parameterized by the above two parameters do not admit fixed-parameter tractable algorithms. Then, for more special cases parameterized by different constraints on query structures like degree, tree-width and number of variables, the TC-QC problems are still not fixed parameter tractable. Finally, on the positive side, if each data completeness statement has a constant size bound, the parameterized TC-QC problem defined by the query completeness size can be solved by a fixed-parameter tractable algorithm. [ABSTRACT FROM AUTHOR]

In an external contextual grammar with selection, contexts are associated with selection languages, and the context (u , v) can be wrapped around a word w if and only if w belongs to the selection language associated with (u , v). In the papers [1] , [3] , [4] , and [6] , some hierarchies are presented if selection languages are taken from subregular language families, defined by automata-theoretic and combinatorial properties, codes, and ideals. In this paper we merge and complete the hierarchies. [ABSTRACT FROM AUTHOR]

Indexing very large collections of strings, such as those produced by the widespread next generation sequencing technologies, heavily relies on multi-string generalization of the Burrows–Wheeler Transform (BWT): large requirements of in-memory approaches have stimulated recent developments on external memory algorithms. The related problem of computing the Longest Common Prefix (LCP) array of a set of strings is instrumental to compute the suffix-prefix overlaps among strings, which is an essential step for many genome assembly algorithms. In a previous paper, we presented an in-memory divide-and-conquer method for building the BWT and LCP where we merge partial BWTs with a forward approach to sort suffixes. In this paper, we propose an alternative backward strategy to develop an external memory method to simultaneously build the BWT and the LCP array on a collection of m strings of different lengths. The algorithm over a set of strings having constant length k has O (m k l) time and I/O volume, using O (k + m) main memory, where l is the maximum value in the LCP array. [ABSTRACT FROM AUTHOR]

Due to the advancement of cloud computing, public key encryption with equality test has become a hot topic in the cryptography community. The notion was extended to the identity-based setting to obtain a new primitive, called identity-based encryption with equality test (IBEET). To the best of our knowledge, there are two categories of authorization mechanisms for IBEET: ciphertext-specified authorization and user-specified authorization. However, these authorizations are not applicable for some scenarios. Motivated by this, we propose in this paper a new primitive, called identity-based encryption with equality test and datestamp-based authorization mechanism (IBEET-DBA). In the primitive, the data owner can control the validity of trapdoor by embedding datestamp into it. The cloud server can only obtain the correct equivalence results on the ciphertexts which are generated within the valid period of trapdoor. In this paper, we formally define this primitive and its security notion. Moreover, we propose the first IBEET-DBA scheme and prove its security. [ABSTRACT FROM AUTHOR]

A ladder lottery, known as "Amidakuji" in Japan, is a common way to decide an assignment at random. A ladder lottery L of a given permutation is optimal if L has the minimum number of horizontal lines. In this paper, we investigate a reconfiguration problem of optimal ladder lotteries. The reconfiguration problem on a set of optimal ladder lotteries asks, given two optimal ladder lotteries L , L ′ of a permutation π , to find a sequence of 〈 L 1 , L 2 , ... , L k 〉 of optimal ladder lotteries of π such that (1) L 1 = L and L k = L ′ and (2) L i for i = 2 , 3 , ... , k is obtained from L i − 1 by moving a bar in L i − 1 locally. An existing result implies that any two optimal ladder lotteries of a permutation π have a reconfiguration sequence of length O (n 3) , where n is the number of elements in π. In this paper, we characterize the minimum length of reconfiguration sequences between two optimal ladder lotteries. Moreover, we present a linear-time algorithm that computes the minimum length. [ABSTRACT FROM AUTHOR]

• The longest cycle problem on interval graphs is solvable in the first simple polynomial algorithm. • The properties of normal orderings of interval graphs are proposed to solve the longest cycle problem. • The longest Hamiltonian connected subgraph problem on interval graphs may be solved by using a similar approach. The longest cycle problem is the problem of finding a cycle with maximal vertices in a graph. Although it is solvable in polynomial time on few trivial graph classes, the longest cycle problem is well known as NP-complete. A lot of efforts have been devoted to the longest cycle problem. To the best of our knowledge however, there are no polynomial algorithms that can solve any of the non-trivial graph classes. Interval graphs, the intersection of chordal graphs and asteroidal triple-free graphs, are known to be the non-trial graph classes that have polynomial algorithm of the longest cycle problem. In 2009, K. Ioannidou, G.B. Mertzios and S.D. Nikolopoulos presented a polynomial algorithm for the longest path problem on interval graphs in Ioannidou et al. (2009) [19]. Inspired by their work, we investigate the longest cycle problem of interval graphs. In this paper, we present the first polynomial algorithm for the longest cycle problem on interval graphs. A dynamic programming approach is proposed in the polynomial algorithm that runs in O (n 8) time, where n is the number of vertices of the input graph. Using a similar approach, we design a polynomial algorithm to solve the longest k -thick subgraph problem on interval graphs which will be presented in another separate work. According to the interesting properties of k -thick interval graphs that we discovered (e.g., an interval graph G is traceable if and only if G is 1-thick, G is hamiltonian if and only if G is 2-thick, G is hamiltonian connected if and only if G is 3-thick and so on), the algorithm presented in this paper can be important in studying the spanning connectivity on interval graphs. [ABSTRACT FROM AUTHOR]

This paper revisits the widely researched gathering problem for two robots without any agreement on the coordinate system in a scenario which allows randomization in the asynchronous scheduling model. The scheduler is considered to be the adversary which determines the activation schedule of the robots. The adversary comes in three flavors, namely, adaptive offline, adaptive online, and oblivious, based on the knowledge of the outcome of random bits. The robots follow wait-look-compute-move cycle. In this paper, we classify the problems based on the capability of the adversary to control the parameters such as wait time, computation delay and the speed of robots and check the feasibility of gathering in terms of adversarial knowledge and capabilities. First, we show the impossibility of gathering under an adaptive offline adversary with non-negative wait time and non-negative computation delay. Gradually relaxing the adversarial capabilities, we present impossibility of gathering for finite random choices and improbability for infinite random choices for an adaptive online adversary. Under an oblivious adversary, we establish the possibility of gathering with zero computation delay. We improve the runtime of the algorithm by restricting the oblivious adversary to choose wait time and computation delay such that the sum of wait time and computation delay is more than a positive constant. Finally, we also extend our algorithm for multiple robots with merging. [ABSTRACT FROM AUTHOR]

• A lower bound for sampling cost of the range partitioning algorithm in the RAM model is proved. • Two lower bounds for sublinear external range partitioning algorithms are proved. • A sublinear external range partitioning algorithm for a novel data distribution is designed. Range partitioning is a typical and mostly used data partitioning method and has became a core operation in most of big data computing platforms. Given an input L of N data items admitting a total order, the goal of range partitioning is to divide the whole input into k ranges containing the same number of data items. There is a trivial lower bound Ω (N) for the exact partitioning algorithms, since they need to at least make a full scan of the whole data. In the context of big data computing, even algorithms with O (N) time are not always thought to be efficient enough, the ultimate goal of designing algorithms on big data is usually to solve problems within sublinear time. Therefore, it is well motivated and important to study sublinear algorithms for the range partitioning problem. The paper aims to answer three questions. For the internal memory (RAM) model, since sophisticated sampling based (ϵ , δ) -approximation partitioning algorithm with O (k log ⁡ (N / δ) ϵ 2 ) time cost has been proposed, the first question is what a lower bound we can obtain for sublinear partitioning algorithms. For the external memory (I/O) model, as far as we know, no previous works give external partitioning algorithms with performance guarantee within sublinear time, therefore the two questions are what the upper bound and the lower bound we can achieve for sublinear external partitioning algorithms. To answer the above questions, based on the RAM and I/O model, the paper studies the lower and upper bounds for the range partitioning problem. For the RAM model, a lower bound Ω (k (1 − δ) ϵ 2 ) for the cost of sampling based partitioning algorithms is proved. For the I/O model, two lower bounds of the sampling cost required by sublinear external range partitioning algorithms are proved, which indicate that at least a full scan of the whole input is needed in the worst case and a general sublinear external partitioning algorithm does not exist. Motivated by the hard instances utilized in the proof of lower bounds, a model for describing the input distributions of the range partitioning problem in practical applications is proposed. Finally, for the special cases described by the model, a sublinear external partitioning algorithm with O (k log ⁡ (N / δ) w B ϵ 2 ) I/O cost is designed. [ABSTRACT FROM AUTHOR]