Search

A connected component of a vertex-coloured graph is said to be colourful if all its vertices have different colours. By extension, a graph is colourful if all its connected components are colourful. Given a vertex-coloured graph $G$ and an integer $p$, the Colourful Components problem asks whether there exist at most $p$ edges whose removal makes $G$ colourful and the Colourful Partition problem asks whether there exists a partition of $G$ into at most $p$ colourful components. In order to refine our understanding of the complexity of the problems on trees, we study both problems on $k$-caterpillars, which are trees with a central path $P$ such that every vertex not in $P$ is within distance $k$ from a vertex in $P$. We prove that Colourful Components and Colourful Partition are NP-complete on $4$-caterpillars with maximum degree $3$, $3$-caterpillars with maximum degree $4$ and $2$-caterpillars with maximum degree $5$. On the other hand, we show that the problems are linear-time solvable on $1$-caterpillars. Hence, our results imply two complexity dichotomies on trees: Colourful Components and Colourful Partition are linear-time solvable on trees with maximum degree $d$ if $d \leq 2$ (that is, on paths), and NP-complete otherwise; Colourful Components and Colourful Partition are linear-time solvable on $k$-caterpillars if $k \leq 1$, and NP-complete otherwise. We leave three open cases which, if solved, would provide a complexity dichotomy for both problems on $k$-caterpillars, for every non-negative integer $k$, with respect to the maximum degree. We also show that Colourful Components is NP-complete on $5$-coloured planar graphs with maximum degree $4$ and on $12$-coloured planar graphs with maximum degree $3$. Our results answer two open questions of Bulteau et al. mentioned in [30th Annual Symposium on Combinatorial Pattern Matching, 2019].

Volume segmentation based on surface attributes is an essential problem in multi-material fabrication and model packing. In practice, current mainstream fabrication techniques have difficulties in yielding models with diverse surface attributes in one pass owing to their craft limitations, making model segmentation a sensible choice for model realization. Partitioning 3D objects into single-attribute volumetric parts prevents fabricating models with different material in a single printing procedure, whereas the arisen challenge is to determine a reliable segmentation solution that is able to handle complicated models in various use scenarios. To achieve this goal, we propose a novel volume partition algorithm generating feasible volumetric parts, each of which is affiliated with one single surface attribute. Our technique enables model segmentation with least conflict and constrained wall thickness so that each volumetric segment can be realized independently by 3D-printing. Generally, it starts with computing a partition proposal guided by radial-based-function iso-surface, then optimizes segmentation interface with a prescribed minimal printing thickness to produce high-quality surface for every volumetric part, and finally splits unextractable volumetric parts into smaller sub-volumes to ensure assemblability of the whole model. As previous methods do not work well in optimizing segment interface for printing, we propose a differential evolution based smoothing algorithm to generate smooth and continuous interface, declining the risk of collision between adjacent volumetric parts. Extensive experimental results are provided in this paper to demonstrate the effectiveness and quality of our proposed technique, showing its advantages on model manufacture over prior methods.

A real symmetric matrix A is copositive if $$x^\top Ax\ge 0$$ x ⊤ A x ≥ 0 for all $$x\ge 0$$ x ≥ 0 . As A is copositive if and only if it is copositive on the standard simplex, algorithms to determine copositivity, such as those in Sponsel et al. (J Glob Optim 52:537–551, 2012) and Tanaka and Yoshise (Pac J Optim 11:101–120, 2015), are based upon the creation of increasingly fine simplicial partitions of simplices, testing for copositivity on each. We present a variant that decomposes a simplex $$\bigtriangleup $$ △ , say with n vertices, into a simplex $$\bigtriangleup _1$$ △ 1 and a polyhedron $$\varOmega _1$$ Ω 1 ; and then partitions $$\varOmega _1$$ Ω 1 into a set of at most $$(n-1)$$ ( n - 1 ) simplices. We show that if A is copositive on $$\varOmega _1$$ Ω 1 then A is copositive on $$\bigtriangleup _1$$ △ 1 , allowing us to remove $$\bigtriangleup _1$$ △ 1 from further consideration. Numerical results from examples that arise from the maximum clique problem show a significant reduction in the time needed to establish copositivity of matrices.

This work addresses the balanced connected k -partition problem ( BCP k ), which is formally defined as follows. Given a connected graph G = ( V , E ) with nonnegative weights on the vertices, find a partition { V i } i = 1 k of V such that each class V i induces a connected subgraph of G , and the weight of a class with the minimum weight is as large as possible. This problem, known to be NP -hard, has been largely investigated under different approaches and perspectives: exact algorithms, approximation algorithms for some values of k or special classes of graphs, and inapproximability results. On the practical side, BCP k is used to model many applications arising in image processing, cluster analysis, operating systems and robotics. We propose three linear programming formulations for BCP k . The first one contains only binary variables and a potentially large number of constraints that can be separated in polynomial time in the corresponding linear relaxation. We introduce new valid inequalities and design polynomial-time separation algorithms for them. The other two formulations are based on flows and have a polynomial number of constraints and variables. Our computational experiments show that the exact algorithms based on the proposed formulations outperform the other exact approaches presented in the literature.

Graph partitioning has been studied in the discipline between computer science and applied mathematics. It is a technique to distribute the whole graph data as a disjoint subset to a different device. The minimum graph partition problem with respect to an independence system of a graph has been studied in this paper. The considered independence system consists of one of the independent sets defined by Boutin. We solve the minimum partition problem in path graphs, cycle graphs, and wheel graphs. We supply a relation of twin vertices of a graph with its independence system. We see that a maximal independent set is not always a minimal set in some situations. We also provide realizations about the maximum cardinality of a minimum partition of the independence system. Furthermore, we study the comparison of the metric dimension problem of a graph with the minimum partition problem of that graph.

Most of today's smart grids are highly vulnerable to cascading failure attacks in which the failure of one or more critical components may trigger the sequential failure of other components, resulting in the eventual breakdown of the whole system. Existing works design different ranking methods for critical node or link identifications that fail to identify potential cascading failure attacks. In this work, we first consider the system from the attacker's point of view with a limited attack budget to study the smart grid vulnerability, referred to as Maximum-Impact through Critical-Line with Limited Budget (MICLLB) problem. We propose an efficient algorithm by considering the interdependency property of the system, called Greedy Based Partition Algorithm (GBPA) to solve the MICLLB problem. In addition, we design an algorithm, namely Homogeneous-Equality Based Defense Algorithm (HEBDA) to help reduce damages in case the system is suffering from the cascading failure attacks. Through rigorous theoretical analysis and experimentation, we demonstrate that the investigated problem is NP-complete problem and our proposed methods perform well within reasonable bounds of computational complexity.

Aim: The main motive of this study is to perform Adaptive Multi Rate Wideband (AMR-WB) Speech Steganography in network security to produce the stego speech with less loss of quality while increasing embedding capacities. Materials and Methods: TIMIT Acoustic-Phonetic Continuous Speech Corpus dataset consists of about 16000 speech samples out of which 1000 samples are taken and 80% pretest power for analyzing the speech steganography. AMR-WB Speech steganography is performed by Diameter Neighbor codebook partition algorithm (Group 1) and Neighbor Index Division codebook division algorithm (Group 2). Results: The AMR-WB speech steganography using DN codebook partition obtained average quality rate of 2.8893 and NID codebook division algorithm obtained average quality rate of 2.4196 in the range of 300bps embedding capacity. Conclusion: The outcomes of this study proves that the decrease in quality in NID is twice more than the DN based steganography while increasing the embedding capacities.

Testing provides essential information for managing infectious disease outbreaks, such as the COVID‐19 pandemic. When testing resources are scarce, an important managerial decision is who to test. This decision is compounded by the fact that potential testing subjects are heterogeneous in multiple dimensions that are important to consider, including their likelihood of being disease‐positive, and how much potential harm would be averted through testing and the subsequent interventions. To increase testing coverage, pooled testing can be utilized, but this comes at a cost of increased false‐negatives when the test is imperfect. Then, the decision problem is to partition the heterogeneous testing population into three mutually exclusive sets: those to be individually tested, those to be pool tested, and those not to be tested. Additionally, the subjects to be pool tested must be further partitioned into testing pools, potentially containing different numbers of subjects. The objectives include the minimization of harm (through detection and mitigation) or maximization of testing coverage. We develop data‐driven optimization models and algorithms to design pooled testing strategies, and show, via a COVID‐19 contact tracing case study, that the proposed testing strategies can substantially outperform the current practice used for COVID‐19 contact tracing (individually testing those contacts with symptoms). Our results demonstrate the substantial benefits of optimizing the testing design, while considering the multiple dimensions of population heterogeneity and the limited testing capacity.

Jelen cikkben a klasszikus klaszterező algoritmusok egy módosítását mutatom be. A cikkben egy olyan módszert mutatok be, amellyel a klaszterező algoritmusok maguk határozzák meg a klaszterhatárokat, azt, hogy hány csoportra bontsák az adatsor elemeit. A klaszterezés egy olyan adatbányászati módszer, ahol az egymással hasonló elemek azonos klaszterbe, míg az egymástól különböző elemek külön klaszterbe kerülnek. Jelen cikkben egy partíciós algoritmust (K-Means) és a hierarchikus módszereket (Single Linkage, Complete Linkage, Average Linkage, Ward, Centroid) mutatom be. A futási eredmények azt mutatják, hogy a klaszterezési algoritmusoknak többé-kevésbé sikerült kialakítaniuk a klasztereket anélkül, hogy bemenetként a klaszterszámot várnánk.

The maximum duo-preservation string mapping (Max-Duo) problem is the complement of the well studied minimum common string partition problem, both of which have applications in many fields including text compression and bioinformatics. k-Max-Duo is the restricted version of Max-Duo, where every letter of the alphabet occurs at most k times in each of the strings, which is readily reduced into the well known maximum independent set (MIS) problem on a graph of maximum degree $$\Delta \le 6(k-1)$$ . In particular, 2-Max-Duo can then be approximated arbitrarily close to 1.8 using the state-of-the-art approximation algorithm for the MIS problem on bounded-degree graphs. 2-Max-Duo was proved APX-hard and very recently a $$(1.6 + \epsilon )$$ -approximation algorithm was claimed, for any $$\epsilon > 0$$ . In this paper, we present a vertex-degree reduction technique, based on which, we show that 2-Max-Duo can be approximated arbitrarily close to 1.4.

In this paper we define a generalization of the classical vertex coloring problem of a graph, where some pairs of adjacent vertices can be assigned to the same color. We call weak an edge connecting two such vertices. We look for a coloring of the graph minimizing the number of weak edges having its endpoints assigned to the same color. This problem is called the minimum chromatic violation problem (MCVP). We present an integer programming formulation for this problem and provide an initial polyhedral study of the polytope arising from this formulation. We give partial characterizations of facet-inducing inequalities and we show how facets from different instances of MCVP are related. We then introduce general lifting procedures which generate (sometimes facet-inducing) valid inequalities from generic valid inequalities. We exhibit several facet-inducing families arising from these procedures and we present a family of facet-inducing inequalities which is not obtained from the prior lifting procedures, associated with certain substructures in the given graph. Finally, we analyze the extreme case of all weak edges and its relationship with the well-known k -partition problem.

The single-sensor Poisson multi-Bernoulli (MB) mixture (PMBM) filter has been developed for multi-target tracking (MTT). However, there is a lack of research on the multi-sensor (MS) extensions of this filter. Because the conjugate density of PMBM filter is a hybrid form, which makes it difficult to extend directly using existing methods. In this study, a general MS Poisson MB filter based on an MS measurement likelihood is derived for MS-MTT. The MB mixture in the PMBM conjugate posterior is approximated as a single MB after each measurement update step. The likelihood function is designed for the partitioned measurements. Firstly, the authors employ the greedy measurement partition algorithm to derive an efficient implementation method; a Gibbs sampler is used to solve the data association problem subsequently. Secondly, they design a novel partition mechanism based on the Gibbs sampling algorithm dealing with those measurements generated by close targets. Various performance simulation and analysis are given in Sections 5 and 6, respectively.

In distributed in-memory computing systems, data distribution has a large impact on performance. Designing a good partition algorithm is difficult and requires users to have adequate prior knowledge of data, which makes data skew common in reality. Traditional approaches to handling data skew by sampling and repartitioning often incur additional overhead. In this paper, we proposed a dynamic execution optimization for the aggregation operator, which is one of the most general and expensive operators in Spark SQL. Our optimization aims to avoid the additional overhead and improve the performance when data skew occurs. The core idea is task stealing. Based on the relative size of data partitions, we add two types of tasks, namely segment tasks for larger partitions and stealing tasks for smaller partitions. In a stage, stealing tasks could actively steal and process data from segment tasks after processing their own. The optimization achieves significant performance improvements from 16% up to 67% on different sizes and distributions of data. Experiments show that involved overhead is minimal and could be negligible.

Versatile video coding (VVC) achieves enormous improvement over the advanced high efficiency video coding (HEVC) standard due to the adoption of the quadtree with nested multi-type tree (QTMT) partition structure and other coding tools. However, the computational complexity increases dramatically as well. To tackle this problem, we propose a decision tree accelerated coding tree units (CTU) partition algorithm for intra prediction in VVC. Firstly, specially designated image features are extracted to characterize the coding unit (CU) complexity. Then, the trained decision tree is employed to predict the partition results. Finally, based on our newly designed intra prediction framework, the partition process is early terminated or redundant partition modes are screened out. The experimental results show that the proposed algorithm could achieve around 52% encoding time reduction for various test video sequences on average with only 1.75% Bjontegaard delta bit rate increase compared with the reference test model VTM9.0 of VVC.

Suppose that we are given a graph whose each vertex is either a supply vertex or a demand vertex and is assigned a nonnegative integer supply or demand value. We consider partitioning G into connected components by removing edges from G so that each connected component has exactly one supply vertex and there exists a flow in each connected component satisfying the supply/demand constraints. The problem that determines the existence of such a partition is called the partition problem. Ito et al. (2005) showed that the partition problem is NP -complete in general and it can be solved in linear time if the given graph is a tree. When the graph does not have such a partition, we scale the demand values uniformly by scale factor r so that the obtained graph has a desired partition. The maximum supply rate problem is the problem that finds the maximum value of such r. Whereas the maximum supply rate problem is NP -hard in general in the same way as the partition problem, Morishita and Nishizeki (2015) gave a weakly polynomial-time algorithm for the problem on trees. In this paper, we give a first strongly polynomial-time algorithm for the maximum supply rate problem on trees. Our algorithm is based on the dynamic programming technique, in which we compute “surplus” and “deficit” of the supply in subproblems from leaves to the root. We use piecewise linear functions of r to represent them, and one of our important contributions is to bound the size of the representation of each function.

The quick and intelligent requests and answers in artificial intelligence (AI) are inseparable from intelligent data. Knowledge graph makes data more intelligent by establishing association among data, which provides convenience for intelligent search, reasoning and analysis of data. Resource Description Framework (RDF) is an effective data representation model of knowledge graph. This paper takes RDF as the research object and proposes an incremental partition method of intelligent data (IPID) to realize the distributed storage of large-scale AI data. First, IPID gives a mixed object function integrating edge cut and load balancing. Second, IPID devises the initial and incremental partitioning algorithms of RDF. The initial partition divides the original RDF graph into kernel vertices, boundary vertices and free vertices. The boundary and freedom nodes select the kernel vertex with the maximum gain of object function to form a sub-partition. And the incremental partition is in charge of the selection of sub-partition of new and deleted data by the object function. Meanwhile, the incremental partition algorithm would also execute a dynamic adjustment strategy at a certain time interval according to the balance and tightness of sub-partition to satisfy the partitioning object. Finally, IPID is tested on the knowledge graph datasets. The experimental results show that the object function guarantees the quality of knowledge graph partition in edge cut and load balancing, and effectively realizes the incremental partition.

Centralized publishing of big location data provides great convenience for various location-based interactive queries and services. Privacy protection of users' location information is an indispensable issue in the security of big data applications. Partition publishing is an effective way to release statistical information of two-dimensional big location data. By combining with the differential privacy model, it can provide more accurate range counting query service on the premise of ensuring location privacy. In order to further improve the availability of location data subsequent to centralized publishing, this paper analyzes the primary noise sources of partition publishing and discusses the constraints among publishing errors, the spatial partition structure, and privacy budget allocation. An unbalanced quadtree partition algorithm based on regional uniformity is proposed. Accordingly, the gradient privacy budget allocation scheme and adjustment method are designed to ensure the effectiveness of the differential privacy model. Experimental comparison of the real-world datasets proves the advantages of the proposed algorithm in improving the querying accuracy of the published data.

The Minimum Sum Coloring Problem (MSCP) and Optimum Cost Chromatic Partition Problem (OCCP), variants of the well-known Graph Coloring Problem (GCP), find applications in different domains, such as VLSI design, resource allocation, scheduling, and so on. MSCP and OCCP are much harder than GCP and solving them for large graphs is particularly challenging. In the literature, much effort has been spent to develop upper and lower bounds for MSCP. Lower bounds for MSCP are not only interesting in theory but also useful in practice: lower bounds can be used to accelerate solvers for MSCP and evaluate the quality of heuristic results. In this paper, we propose two new theoretical lower bounds for MSCP and OCCP by exploiting structural properties of them. The two lower bounds are based on (relaxed) values of the chromatic number, independence number and bipartite number of the graph. Experiments on standard benchmarks DIMACS and COLOR show that our lower bounds can improve previous known theoretical and computational lower bounds for MSCP on at least 22% of the benchmark instances.

In the planted partition problem, the $n$ vertices of a random graph are partitioned into $k$ "clusters," and edges between vertices in the same cluster and different clusters are included with constant probability $p$ and $q$, respectively (where $0 \le q < p \le 1$). We give an efficient spectral algorithm that recovers the clusters with high probability, provided that the sizes of any two clusters are either very close or separated by $\geq \Omega(\sqrt n)$. We also discuss a generalization of planted partition in which the algorithm's input is not a random graph, but a random real symmetric matrix with independent above-diagonal entries. Our algorithm is an adaptation of a previous algorithm for the uniform case, i.e., when all clusters are size $n / k \geq \Omega(\sqrt n)$. The original algorithm recovers the clusters one by one via iterated projection: it constructs the orthogonal projection operator onto the dominant $k$-dimensional eigenspace of the random graph's adjacency matrix, uses it to recover one of the clusters, then deletes it and recurses on the remaining vertices. We show herein that a similar algorithm works in the nonuniform case., Comment: 22 pages, 4 figures

Given an undirected graph, a star partition is a partition of the nodes into subsets with at least two nodes so that the subgraph induced by each subset has a spanning star. Star partitions are related to well-known problems concerning domination in graphs and edge covering. We focus on the Constrained Star Partition Problem (CSP) that asks for finding a star partition of given cardinality. The problem is new and presents interesting peculiarities. We explore the relation between the cardinalities of star partitions and domatic bipartitions, showing that there are star partitions of any cardinality between minimum and maximum values, and that a similar but weaker result holds for domatic bipartitions. We study the computational complexity of different versions of star partition and domatic bipartition problems, proving that most of them, in particular CSP, constrained domatic bipartition and balanced domatic bipartition, are NP-complete. We also show that star partition problems are polynomial on trees and, more generally, on bounded treewidth graphs. We introduce an integer linear programming formulation that defines a polytope containing all the star partitions of a graph, showing that its vertices have only integral components for trees, which implies that linear programming can be used to solve weighted star partition problems on trees.

The minimum k-partition problem is a challenging combinatorial problem with a diverse set of applications ranging from telecommunications to sports scheduling. It generalizes the max-cut problem and has been extensively studied since the late sixties. Strong integer formulations proposed in the literature suffer from a large number of constraints and variables. In this work, we introduce two more compact integer linear and semidefinite reformulations that exploit the sparsity of the underlying graph and develop theoretical results leveraging the power of chordal decomposition. Numerical experiments show that the new formulations improve upon state-of-the-art.

Malware homology identification is important in attacking event tracing, emergency response scheme generation, and event trend prediction. Current malware homology identification methods still rely on manual analysis, which is inefficient and cannot respond quickly to the outbreak of attack events. In response to these problems, we propose a new malware homology identification method from a gene perspective. A malware gene is represented by the subgraph, which can describe the homology of malware families. We extract the key subgraph from the function dependency graph as the malware gene by selecting the key application programming interface (API) and using the community partition algorithm. Then, we encode the gene and design a frequent subgraph mining algorithm to find the common genes between malware families. Finally, we use the family genes to guide the identification of malware based on homology. We evaluate our method with a public dataset, and the experiment results show that the accuracy of malware classification reaches 97% with high efficiency.

In the study of the long-term prediction of time series with high noise and nonlinearity, the trend information and fluctuation range of the sequence data is usually more valuable and practical than the forecasting of the specific values at time points. A method named as stepwise linear division (SLD) is constructed for the variable-length partition of fuzzy information granule (FIG), characteristics of which are extracted from the original data distribution of time series. Secondly, based on the above partition algorithm, a novel fuzzy information granule is first proposed, which can characterize the variant trend of the data, the range of fluctuation and the degree of dispersion. Moreover, the reliability of the prediction results can be quantified. After granulating time series, a rule-based fuzzy inference system is established to achieve the prediction of time series. Synthetic sequences and real-life time series, including chaotic Mackey–Glass time series, temperature, sunspot numbers, milk production and financial data are utilized in experiments to verify the effectiveness of the proposed scheme. The experimental results demonstrate that the proposed model can contain more rich semantic information and produce better long-term prediction performance compared with existing numeric models and fuzzy inference systems.

This study aims to solve the problem of detecting anomalies in big data. A border-based Gird Partition (BGP) algorithm was proposed. The BGP algorithm focuses on calculating the Local Outlier Factor (LOF) for big data in a distributed environment. It splits the data into intersected subsets, then allocates these subsets to the slave nodes in a distributed environment. Some parts of these subsets are replicated between slave nodes. The slave nodes calculate the LOF for each subset that it owns. The splitting of the data between the slave nodes is done in grid-based without considering the size of the data that will be assigned to every slave node. The BGP algorithm results in un-balanced distribution of the subsets between slave nodes. To overcome this problem a modification on the BGP algorithm is proposed to take in consideration the size of the data that will be assigned to every slave node. The modified algorithm called Balanced boarder-based Gird Partition algorithm (BBGP). BBGP splits the data between the slave node equally. So that all the slave nodes will do balanced processing for calculating the LOF for the data. In the end, we evaluate the performance of the two algorithms through a series of simulation experiments over real data sets.

In 1996, Michael Stiebitz proved that if G is a simple graph with δ ( G ) ≥ s + t + 1 and s , t ∈ Z 0 , then V ( G ) can be partitioned into two sets A and B such that δ ( G [ A ] ) ≥ s and δ ( G [ B ] ) ≥ t . In 2016, Amir Ban proved a similar result for weighted graphs. Let G be a simple graph with at least two vertices, let w : E ( G ) → R > 0 be a weight function, let s , t ∈ R ≥ 0 , and let W = max e ∈ E ( G ) w ( e ) . If δ ( G ) ≥ s + t + 2 W , then V ( G ) can be partitioned into two sets A and B such that δ ( G [ A ] ) ≥ s and δ ( G [ B ] ) ≥ t . This motivated us to consider this partition problem for multigraphs, or equivalently for weighted graphs ( G , w ) with w : E ( G ) → Z ≥ 1 . We prove that if s , t ∈ Z ≥ 0 and δ ( G ) ≥ s + t + 2 W − 1 ≥ 1 , then V ( G ) can be partitioned into two sets A and B such that δ ( G [ A ] ) ≥ s and δ ( G [ B ] ) ≥ t . We also prove a variable version of this result and show that for K 4 − -free graphs, the bound on the minimum degree can be decreased.

The coordinates of nodes are very important in the application of wireless sensor networks (WSN). The range-free localization algorithm is the best method to obtain the coordinates of sensor nodes at present. Range-free localization algorithm can be divided into two stages: distance estimation and coordinate calculation. For reduce the error in the distance estimation stage, a node localization algorithm for WSN based on virtual partition and distance correction (VP-DC) is proposed in this paper. In the distance estimation stage, firstly, the distance of each hop on the shortest communication path between the unknown node and the beacon node is calculated with the employment of virtual partition algorithm, then, the length of the shortest communication path is obtained by summing the distance of each hop, finally, the unknown distance between nodes is obtained according to the optimal path search algorithm and the distance correction formula. This paper innovative proposes the virtual partition algorithm and the optimal path search algorithm, which effectively avoids the distance estimation error caused by hop number and hop distance, and improves the localization accuracy of unknown nodes.

Graph partition is a classical combinatorial optimization and graph theory problem, and it has a lot of applications, such as scientific computing, VLSI design and clustering etc. In this paper, we study the partition problem on large scale directed graphs under a new objective function, a new instance of graph partition problem. We firstly propose the modeling of this problem, then design an algorithm based on multi-level strategy and recursive partition method, and finally do a lot of simulation experiments. The experimental results verify the stability of our algorithm and show that our algorithm has the same good performance as METIS. In addition, our algorithm is better than METIS on unbalanced ratio.

The balanced connected k-partition (BCPk) problem consists in partitioning a connected graph into connected subgraphs with similar weights. This problem arises in multiple practical applications, such as police patrolling, image processing, data base and operating systems. In this work, we address the BCPk using mathematical programming. We propose a compact formulation based on flows and a formulation based on separators. We introduce classes of valid inequalities and design polynomial-time separation routines. Moreover, to the best of our knowledge, we present the first polyhedral study for BCPk in the literature. Finally, we report on computational experiments showing that the proposed algorithms significantly outperform the state of the art for BCPk.

In this paper we consider an online version of different colouring problems in overlap graphs, motivated by some stacking problems. The instance is a system of time intervals presented in non-decreasing order of the left endpoint. We consider the usual colouring problem as well as b-bounded colouring (colour class have a maximum capacity b) and the same problems in the complement graph. We also consider the case where at most b intervals of the same colour can intersect. For all these versions we obtain a logarithmic competitive ratio w.r.t. the maximum ratio of interval lengths while the best known ratio for the usual colouring was linear. To our knowledge it is the first time the other variants are considered in online overlap graphs. Moreover, in the offline case, a pre-processing allows us to deduce a logarithmic approximation ratio w.r.t. the maximum number of pairwise disjoint intervals in the system. Our method is based on a partition of the overlap graph into permutation graphs, leading to a competitive-preserving reduction of the problem in overlap graphs to the same problem in permutation graphs. We think that this new partition problem by itself is of interest for future work.

A bounded cost path planning method is developed for underwater vehicles assisted by a data-driven flow modeling method. The modeled flow field is partitioned as a set of cells of piece-wise constant flow speed. A flow partition algorithm and a parameter estimation algorithm are proposed to learn the flow field structure and parameters with justified convergence. A bounded cost path planning algorithm is developed taking advantage of the partitioned flow model. An extended potential search method is proposed to determine the sequence of partitions that the optimal path crosses. The optimal path within each partition is then determined by solving a constrained optimization problem. Theoretical justification is provided for the proposed extended potential search method generating the optimal solution. The path planned has the highest probability to satisfy the bounded cost constraint. The performance of the algorithms is demonstrated with experimental and simulation results, which show that the proposed method is more computationally efficient than some of the existing methods.

This paper presents the concept and algorithm of data mining and focuses on the linear regression algorithm. Based on the multiple linear regression algorithm, many factors affecting CET4 are analyzed. Ideas based on data mining, collecting history data and appropriate to transform, using statistical analysis techniques to the many factors influencing the CET-4 test were analyzed, and we have obtained the CET-4 test result and its influencing factors. It was found that the linear regression relationship between the degrees of fit was relatively high. We further improve the algorithm and establish a partition-weighted K-nearest neighbor algorithm. The K-weighted K nearest neighbor algorithm and the partition algorithm are used in the CET-4 test score classification prediction, and the statistical method is used to study the relevant factors that affect the CET-4 test score, and screen classification is performed to predict when the comparison verification will pass. The weight K of the input feature and the adjacent feature are weighted, although the allocation algorithm of the adjacent classification effect has not been significantly improved, but the stability classification is better than K-nearest neighbor algorithm, its classification efficiency is greatly improved, classification time is greatly reduced, and classification efficiency is increased by 119%. In order to detect potential risk graduating students earlier, this paper proposes an appropriate and timely early warning and preschool K-nearest neighbor algorithm classification model. Taking test scores or make-up exams and re-learning as input features, the classification model can effectively predict ordinary students who have not graduated.

Acoustic array is a ubiquitous tool for locating and quantifying sound sources. However, its effectiveness depends greatly on the array configuration. This paper presents an array configuration method to enhance array performance, especially on the spatial resolution and the Doppler effect correction. The problem of array configuration is formulated into a position matrix determined by introducing partition spatial filtering. Irregular coaxial ring grid spacings and partition filtering conditions are suggested to control array spatial resolution. Geometrical parameters and performance indicators are constructed to quantify the relationships between the array configuration and performance. Based on these quantitative relations, the spatial variation of the array beam pattern and the Doppler effect has got adaptive adjustment. In particular, an adaptive partition algorithm is proposed to reduce computation time. The performance of the method is examined numerically and experimentally, which is compared with the other methods. The results provide the method to guide the design of a 64-microphone optimized array with high performance (1.8° spatial angle resolution and 40% Doppler frequency correction over the bandwidth from 800 Hz to 3000 Hz) and fast computing speed (18 s array generated time for 2000 arrays). Furthermore, an unusual feature of the method is that it can be utilized in the case when the source moves at a nonconstant velocity.

With the development of multimedia equipment and the increasing demand for high-quality video applications, the traditional video coding standard, H.265/High Efficiency Video Coding (HEVC), can no longer effectively satisfy the requirements. To promote the development of high-quality video, a new generation video coding standard, H.266/Versatile Video Coding (H.266/VVC), is established, and it is the inheritance and development of H.265/HEVC. It not only retains many mature technologies and methods in HEVC but also adds some new coding tools, such as wide-angle prediction and Multitype Tree (MTT) partition structure. The MTT partition structure brings a more flexible partition method of Coding Unit (CU), but the accompanying increase in computational complexity is unacceptable. In order to ensure an effective balance between coding efficiency and coding quality, a fast CU partition algorithm based on texture is proposed in this paper. First, the texture complexity of the neighboring CU is used as a threshold for evaluating the complexity of the current CU, so as to skip the unpromising depth. Then, the gradient features are extracted to determine whether the Quad-Tree (QT) partition is executed. Finally, the improved Canny operator is used to extract edge features, and the partition mode in the horizontal or vertical direction is excluded. The algorithm was embedded in VTM7.0, and the video sequences with different resolutions were tested under general experimental configuration. Simulation experiment results show that the average time saving of this method reached 50.56% compared with the anchor algorithm. At the same time, the average BDBR is increased by 1.31%.

In this paper we investigate the effects of a quantum algorithm which increases the amplitude of the states corresponding to the solutions of the partition problem by a factor of almost two. The study is limited to one iteration.

We establish the existence of solutions to a weakly-coupled competitive system of polyharmonic equations in \begin{document}$ \mathbb{R}^N $\end{document} which are invariant under a group of conformal diffeomorphisms, and study the behavior of least energy solutions as the coupling parameters tend to \begin{document}$ -\infty $\end{document}. We show that the supports of the limiting profiles of their components are pairwise disjoint smooth domains and solve a nonlinear optimal partition problem of \begin{document}$ \mathbb R^N $\end{document}. We give a detailed description of the shape of these domains.

Deep neural networks (DNNs) sustain high performance in today's data processing applications. DNN inference is resource-intensive thus is difficult to fit into a mobile device. An alternative is to offload the DNN inference to a cloud server. However, such an approach requires heavy raw data transmission between the mobile device and the cloud server, which is not suitable for mission-critical and privacy-sensitive applications such as autopilot. To solve this problem, recent advances unleash DNN services using the edge computing paradigm. The existing approaches split a DNN into two parts and deploy the two partitions to computation nodes at two edge computing tiers. Nonetheless, these methods overlook collaborative device-edge-cloud computation resources. Besides, previous algorithms demand the whole DNN re-partitioning to adapt to computation resource changes and network dynamics. Moreover, for resource-demanding convolutional layers, prior works do not give a parallel processing strategy without loss of accuracy at the edge side. To tackle these issues, we propose D3, a dynamic DNN decomposition system for synergistic inference without precision loss. The proposed system introduces a heuristic algorithm named horizontal partition algorithm to split a DNN into three parts. The algorithm can partially adjust the partitions at run time according to processing time and network conditions. At the edge side, a vertical separation module separates feature maps into tiles that can be independently run on different edge nodes in parallel. Extensive quantitative evaluation of five popular DNNs illustrates that D3 outperforms the state-of-the-art counterparts up to 3.4 times in end-to-end DNN inference time and reduces backbone network communication overhead up to 3.68 times., Comment: 11 pages, 13 figures

We consider the {\em vector partition problem}, where $n$ agents, each with a $d$-dimensional attribute vector, are to be partitioned into $p$ parts so as to minimize cost which is a given function on the sums of attribute vectors in each part. The problem has applications in a variety of areas including clustering, logistics and health care. We consider the complexity and parameterized complexity of the problem under various assumptions on the natural parameters $p,d,a,t$ of the problem where $a$ is the maximum absolute value of any attribute and $t$ is the number of agent types, and raise some of the many remaining open problems.

Approximating Subset Sum is a classic and fundamental problem in computer science and mathematical optimization. The state-of-the-art approximation scheme for Subset Sum computes a $(1-\varepsilon)$-approximation in time $\tilde{O}(\min\{n/\varepsilon, n+1/\varepsilon^2\})$ [Gens, Levner'78, Kellerer et al.'97]. In particular, a $(1-1/n)$-approximation can be computed in time $O(n^2)$. We establish a connection to Min-Plus-Convolution, a problem that is of particular interest in fine-grained complexity theory and can be solved naively in time $O(n^2)$. Our main result is that computing a $(1-1/n)$-approximation for Subset Sum is subquadratically equivalent to Min-Plus-Convolution. Thus, assuming the Min-Plus-Convolution conjecture from fine-grained complexity theory, there is no approximation scheme for Subset Sum with strongly subquadratic dependence on $n$ and $1/\varepsilon$. In the other direction, our reduction allows us to transfer known lower order improvements from Min-Plus-Convolution to Subset Sum, which yields a mildly subquadratic randomized approximation scheme. This adds the first approximation problem to the list of problems that are equivalent to Min-Plus-Convolution. For the related Partition problem, an important special case of Subset Sum, the state of the art is a randomized approximation scheme running in time $\tilde{O}(n+1/\varepsilon^{5/3})$ [Mucha~et~al.'19]. We adapt our reduction from Subset Sum to Min-Plus-Convolution to obtain a related reduction from Partition to Min-Plus-Convolution. This yields an improved approximation scheme for Partition running in time $\tilde{O}(n + 1/\varepsilon^{3/2})$. Our algorithm is the first deterministic approximation scheme for Partition that breaks the quadratic barrier.

Multi-robot cooperative patrolling systems have been extensively employed in the civilian and military fields, including monitoring forest fires, marine search-and-rescue, and area patrol. Multi-robot area patrol problems refer to the activity that a team of robots works cooperatively and regularly to visit the key targets in the given area for security. Following consideration of the low cost and high safety of unmanned surface vehicles (USV), a team of USVs is organized to perform area patrol in a sophisticated maritime environment. In this paper, we establish a mathematical model considering the characteristics of the cooperative patrol task and the limited conditions of USVs. A hybrid partition-based patrolling scheme is proposed for a multi-USV system to visit targets with different importance levels in a maritime area. Firstly, a centralized area partition algorithm is utilized to partition the patrolling area according to the number of USVs. Secondly, a distributed path planning algorithm is applied to planning the patrolling path for each USV to visit the targets in a maritime environment to minimize the length of the patrolling path for the USV team. Finally, comparative experiments between the proposed scheme and other methods are carried out to validate the performance of the hybrid partition-based patrolling scheme. Simulation results and experimental analysis show the efficiency of the proposed hybrid partition-based patrolling scheme compared to several previous patrolling algorithms.

Emerging graph neural networks (GNNs) have extended the successes of deep learning techniques against datasets like images and texts to more complex graph-structured data. By leveraging GPU accelerators, existing frameworks combine both mini-batch and sampling for effective and efficient model training on large graphs. However, this setup faces a scalability issue since loading rich vertices features from CPU to GPU through a limited bandwidth link usually dominates the training cycle. In this paper, we propose PaGraph, a system that supports general and efficient sampling-based GNN training on single-server with multi-GPU. PaGraph significantly reduces the data loading time by exploiting available GPU resources to keep frequently accessed graph data with a cache. It also embodies a lightweight yet effective caching policy that takes into account graph structural information and data access patterns of sampling-based GNN training simultaneously. Furthermore, to scale out on multiple GPUs, PaGraph develops a fast GNN-computation-aware partition algorithm to avoid cross-partition access during data parallel training and achieves better cache efficiency. Evaluations on two representative GNN models, GCN and GraphSAGE, show that PaGraph achieves up to 96.8% data loading time reductions and up to 4.8X performance speedup over the state-of-the-art baselines. Together with preprocessing optimization, PaGraph further delivers up to 16.0X end-to-end speedup.

Network update enables Software-Defined Networks (SDNs) to optimize the data plane performance via southbound APIs. The single update between the initial and the final network states fail to handle high-frequency changes or the burst event during the update procedure in time, leading to prolonged update time and inefficiency. On the contrary, the continuous update can respond to the network condition changes at all times. However, existing work, especially "Update Algebra" can only guarantee blackhole- and loop-free. The congestion-free property cannot be respected during the update procedure. In this paper, we propose Coeus, a continuous network update system while maintaining blackhole-, loop- and congestion-free simultaneously. Firstly, we establish an operation-based continuous update model. Based on this model, we dynamically reconstruct an operation dependency graph to capture unexecuted update operations and the link utilization variations. Subsequently, we develop an operation composition algorithm to eliminate redundant update commands and an operation node partition algorithm to speed up the update procedure. We prove that the partition algorithm is optimal and can guarantee the consistency. Finally, extensive evaluations show that Coeus can improve the makespan by at least 179% compared with state-of-the-art approaches when the arrival rate of update events equals to three times per second.

This paper proposes a deep Q network (DQN)-based method for the workload partition problem in OpenCL. The DQN, a reinforcement learning algorithm, optimizes the workload partition for each processing unit by the self-training, based on the accumulated performance data on the computing environment. Our experiments reveal that the DQN-based partition provides the performance improvement by up to 62.2% and 6.9% in JPEG decoding, compared to the LuxMark-based and target-based partitions, respectively. The DQN is able to capture the low-level contention in slave devices such as caches and memory, and the communication bottleneck between devices, and reflect it to the workload partition ratio.

As online social networks play a more and more important role in public opinion, the large-scale simulation of social networks has been focused on by many scientists from sociology, communication, informatics, and so on. It is a good way to study real information diffusion in a symmetrical simulation world by agent-based modeling and simulation (ABMS), which is considered an effective solution by scholars from computational sociology. However, on the one hand, classical ABMS tools such as NetLogo cannot support the simulation of more than thousands of agents. On the other hand, big data platforms such as Hadoop and Spark used to study big datasets do not provide optimization for the simulation of large-scale social networks. A two-tier partition algorithm for the optimization of large-scale simulation of social networks is proposed in this paper. First, the simulation kernel of ABMS for information diffusion is implemented based on the Spark platform. Both the data structure and the scheduling mechanism are implemented by Resilient Distributed Data (RDD) to simulate the millions of agents. Second, a two-tier partition algorithm is implemented by community detection and graph cut. Community detection is used to find the partition of high interactions in the social network. A graph cut is used to achieve the goal of load balance. Finally, with the support of the dataset recorded from Twitter, a series of experiments are used to testify the performance of the two-tier partition algorithm in both the communication cost and load balance.