Localizing Combinatorial Properties for Partitions on Block Graphs

We extend the study on partition properties from the set partition to the graph partition, especially for the class of connected block graphs which includes trees. We introduce seventeen partition properties and determine their inter-relations. The notions of k-consistency and k-sortability were studied in the set partition to localize the properties, i.e., a global property can be verified through checking local conditions. We carry on these studies for partitions on connected block graphs. In particular, we completely determine the consistency for all the seventeen properties.     

A new approach to solve open-partition problems

A partition problem in one-dimensional space is to seek a partition of a set of numbers that maximizes a given objective function. In some partition problems, the partition size, i.e., the number of nonempty parts in a partition, is fixed; while in others, the size can vary arbitrarily. We call the former the size-partition problem and the latter the open-partition problem. In general, it is much harder to solve open problems since the objective functions depend on size. In this paper, we propose a new approach by allowing empty parts and transform the open problem into a size problem allowing empty parts, called a relaxed-size problem. While the sortability theory has been established in the literature as a powerful tool to attack size partition problems, we develop the sortability theory for relaxed-size problems as a medium to solve open problems.     

One-dimensional optimal bounded-shape partitions for Schur convex sum objective functions

Consider the problem of partitioning n nonnegative numbers into p parts, where part i can be assigned n_i numbers with n_i lying in a given range. The goal is to maximize a Schur convex function F whose ith argument is the sum of numbers assigned to part i. The shape of a partition is the vector consisting of the sizes of its parts, further, a shape (without referring to a particular partition) is a vector of nonnegative integers (n₁,..., n_p) which sum to n. A partition is called size-consecutive if there is a ranking of the parts which is consistent with their sizes, and all elements in a higher-ranked part exceed all elements in the lower-ranked part. We demonstrate that one can restrict attention to size-consecutive partitions with shapes that are nonmajorized, we study these shapes, bound their numbers and develop algorithms to enumerate them. Our study extends the analysis of a previous paper by Hwang and Rothblum which discussed the above problem assuming the existence of a majorizing shape. This research is partially supported by ROC National Science grant NSC 92-2115-M-009-014.     

Strongly 2-shape-sortability of vector partitions

Partitioning points optimally in ℝ¹ have been well studied. Hwang et al. (2003) first extended the optimal partitioning problems from ℝ¹ to ℝ^d. In particular, they studied the “sortability” of some partition properties. They also constructed examples to show that some partition properties, like Disjoint and Cone disjoint, are not sortable under some constraints 핊. In this note we construct a more concise example than theirs and also prove that another partition property, Nonpenetrating, is not sortable under 핊.     

On the number of separable partitions

Consider partitions of a given set A of n distinct points in general position in ℝ ^d into parts where each pair of parts can be separated by a hyperplane that contains a given set of points E. We consider the problem of counting and generating all such partitions (correcting a classic 1967 result of Harding about the number of such partitions into two parts). Applications of the result to partition problems are presented.     

An efficient approach for large scale graph partitioning

In this paper, we consider the problem of partitioning the set of vertices of a graph intok subsets of approximately the same cardinality in such a way that the number of edges whose endpoints are in different subsets is minimized. A greedy heuristic, called Procedure1, based on the independent growth of each subset by fronts is proposed for constructing a good-quality graph partition. In addition, we present a more sophisticated version of the greedy heuristic, called Procedure2, which periodically calls a routine to refine the partition being built. We show that the partitions generated by Procedure1 are competitive with those obtained by several constructive heuristics in the literature, e.g. spectral, geometric, as well as other greedy heuristics. Moreover, the partitions produced by Procedure2 are compared with those produced by a leading graph partitioning method in the literature.     

Are there more almost separable partitions than separable partitions?

A partition of a set of n points in d-dimensional space into p parts is called an (almost) separable partition if the convex hulls formed by the parts are (almost) pairwise disjoint. These two partition classes are the most encountered ones in clustering and other partition problems for high-dimensional points and their usefulness depends critically on the issue whether their numbers are small. The problem of bounding separable partitions has been well studied in the literature (Alon and Onn in Discrete Appl. Math. 91:39–51, 1999; Barnes et al. in Math. Program. 54:69–86, 1992; Harding in Proc. Edinb. Math. Soc. 15:285–289, 1967; Hwang et al. in SIAM J. Optim. 10:70–81, 1999; Hwang and Rothblum in J. Comb. Optim. 21:423–433, 2011a). In this paper, we prove that for d≤2 or p≤2, the maximum number of almost separable partitions is equal to the maximum number of separable partitions.     

On the vertex characterization of single-shape partition polytopes

Given a partition of distinct d-dimensional vectors into p parts, the partition sum of the partition is the sum of vectors in each part. The shape of the partition is a p-tuple of the size of each part. A single-shape partition polytope is the convex hull of partition sums of all partitions that have a prescribed shape. A partition is separable if the convex hull of its parts are pairwise disjoint. The separability of a partition is a necessary condition for the associated partition sum to be a vertex of the single-shape partition polytope. It is also a sufficient condition for d=1 or p=2. However, the sufficiency fails to hold for d≥3 and p≥3. In this paper, we give some geometric sufficient conditions as well as some necessary conditions of vertices in general d and p. Thus, the open case for d=2 and p≥3 is resolved.     

Separable Preferences,Strategyproofness, and Decomposability

We consider strategyproof social choice functions defined over product domains. If preferences are strict orderings and separable, then strategyproof social choice functions must be decomposable provided that the domain of preferences is rich. We provide several characterization results in the case where preferences are separable only with respect to the elements of some partition of the set of components and these partitions vary across individuals. We characterize the libertarian social choice function and show that no superset of the tops separable domain admits strategyproof nondictatorial social choice functions.     

Significance of the Dermal Route of Exposure to Risk Assessment

The skin is a route of exposure that needs to be considered when conducting a risk assessment. It is necessary to identify the potential for dermal penetration by a chemical as well as to determine the overall importance of the dermal route of exposure as compared with inhalation or oral routes of exposure. The physical state of the chemical, vapor or liquid, the concentration, neat or dilute, and the vehicle, lipid or aqueous, is also important. Dermal risk is related to the product of the amounts of penetration and toxicity. Toxicity involves local effects on the skin itself and the potential for systemic effects. Dermal penetration is described in large part by the permeability constant. When permeability constants are not known, partition coefficients can be used to estimate a chemical's potential to permeate the skin. With these concepts in mind, a tiered approach is proposed for dermal risk assessment. A key first step is the determination of a skin-to-air or skin-to-medium partition coefficient to estimate a potential for dermal absorption. Building a physiologically-based pharmacokinetic (PBPK) model is another step in the tiered approach and is useful prior to classical in vivo toxicity tests. A PBPK model can be used to determine a permeability constant for a chemical as well as to show the distribution of the chemical systemically. A detailed understanding of species differences in the structure and function of the skin and how they relate to differences in penetration rates is necessary in order to extrapolate animal data from PBPK models to the human. A study is in progress to examine anatomical differences for four species.     

Axiomatic Based Decomposition for Conceptual Product Design

This paper describes a structured methodology for decomposing the conceptual design problem in order to facilitate the design process and result in improved conceptual designs that better satisfy the original customer requirements. The axiomatic decomposition for conceptual design method combines Alexander's network partitioning formulation of the design problem with Suh's Independence Axiom. The axiomatic decomposition method uses a cross‐domain approach in a House of Quality context to estimate the interactions among the functional requirements that are derived from a qualitative assessment of customer requirements. These interactions are used in several objective functions that serve as criteria for decomposing the design network. A new network partitioning algorithm is effective in creating partitions that maximize the within‐partition interactions and minimize the between‐partition interactions with appropriate weightings. The viability, usability, and value of the axiomatic decomposition method were examined through analytic comparisons and qualitative assessments of its application. The new method was examined using students in engineering design capstone courses and it was found to be useable and did produce better product designs that met the customer requirements. The student‐based assessment revealed that the process would be more effective with individuals having design experience. In a subsequent assessment with practicing industrial designers, it was found that the new method did facilitate the development of better designs. An important observation was the need for limits on partition size (maximum of four functional requirements.) Another issue identified for future research was the need for a means to identify the appropriate starting partition for initiating the design.     

基于改进自适应最优分割法的风险预警区间模型研究——针对重大突发公共卫生事件

重大突发公共卫生事件，譬如新型冠状病毒疫情，严重危害着世界各国人民的生命安全，风险预警是构建重大突发公共卫生事件风险预警管控体系的关键所在，而其风险预警区间的精准确定是关乎预警等级的关键问题。基于自适应最优分割模型，引入熵值法计算各指标权重，采用多种函数拟合识别函数特征，构建了改进的自适应最优分割模型，定量科学划分了重大突发公共卫生事件风险预警区间。通过结合实际案例，应用Matlab软件进行仿真，验证了预警区间的吻合度，为构建重大突发公共卫生事件风险预警防控提供了理论参考。     

Common Knowledge with Monotone Statistics

When individual statistics are aggregated through a strictly monotone function to an aggregate statistic, common knowledge of the value of the aggregate statistic does not imply, in general, that the individual statistics are either equal or constant. This paper discusses circumstances where constancy and equality both hold. The first case arises when partitions are independently drawn, and each individual's information is determined by their own partition and some public signal. In this case common knowledge of the value of the aggregator function implies (with probability one) that the individual statistics are constant, so that in the case where the individual statistics have the same expected value, they must all be equal. The second circumstance is where private statistics are related: affiliation of individual statistics and a lattice condition imply that the individual statistics are equal when the value of the aggregate statistic is common knowledge.     

Reduction of the Three-Partition Problem

The three-partition problem is one of the most famous strongly NP-complete combinatorial problems. We introduce properties which, in many cases, can allow either a quick solution of an instance or a reduction of its size. The average effectiveness of the properties proposed is tested through computational experiments.     

Security of Separated Data in Cloud Systems with Competing Attack Detection and Data Theft Processes

Empowered by virtualization technology, service requests from cloud users can be honored through creating and running virtual machines. Virtual machines established for different users may be allocated to the same physical server, making the cloud vulnerable to co‐residence attacks where a malicious attacker can steal a user's data through co‐residing their virtual machines on the same server. For protecting data against the theft, the data partition technique is applied to divide the user's data into multiple blocks with each being handled by a separate virtual machine. Moreover, early warning agents (EWAs) are deployed to possibly detect and prevent co‐residence attacks at a nascent stage. This article models and analyzes the attack success probability (complement of data security) in cloud systems subject to competing attack detection process (by EWAs) and data theft process (by co‐residence attackers). Based on the suggested probabilistic model, the optimal data partition and protection policy is determined with the objective of minimizing the user's cost subject to providing a desired level of data security. Examples are presented to illustrate effects of different model parameters (attack rate, number of cloud servers, number of data blocks, attack detection time, and data theft time distribution parameters) on the attack success probability and optimization solutions.     

经济时间序列的非线性组合建模与预测方法研究

基于模糊系统在紧立集中能够任意逼近非线性连续函数的特性,本文提出了一种基于Takagi-Sugeno模糊规则基的非线性组合预测新方法,以克服线性组合预测方法在解决非平稳时间序列组合建模问题所遇到的困难和存在的不足,并采用相应的遗传算法确定模糊系统的参数及模糊子集的划分。理论分析和大量的应用实例表明:该方法具有很强的学习与泛化能力,在处理诸如经济时间序列这种具有一定程度不确性的非线性系统的组合建模与预测方面有很好的应用价值。     

Finite Order Implications of Common Priors

I characterize the implications of the common prior assumption for finite orders of beliefs about beliefs at a state and show that in finite models, the only such implications are those stemming from the weaker assumption of a common support. More precisely, given any finite N and any finite partitions model where priors have the same support, there is another finite partitions model with common priors that has the same nth order beliefs and knowledge for all n≤N.     

Dermal Uptake of Organic Chemicals from a Soil Matrix

Uptake of chemicals from soil on human skin is considered. Based on a review of literature on the structure of human skin, the processes by which chemicals pass through this boundary, and experiments that reveal the rate and magnitude of this transport process; a two-layer model is presented for estimating how chemical uptake through the stratum corneum depends on chemical properties, skin properties, soil properties and exposure conditions. The model is applied to two limiting scenarios--(1) continuous deposition and removal of soil on the skin surface and (2) a one-time deposition of soil onto the skin surface. The fraction of soil-bound chemical that passes through the stratum corneum is dependent on the skin-soil layer thickness; the dimensionless Henry's law constant, Kh and the octanol-water partition coefficient, Kow of the soil-bound chemical. The nature of this dependence is discussed.