Constrained clustering, such as $k$-means with instance-level Must-Link (ML) and Cannot-Link (CL) auxiliary information as the constraints, has been extensively studied recently, due to its broad applications in data science and AI. Despite some heuristic approaches, there has not been any algorithm providing a non-trivial approximation ratio to the constrained $k$-means problem. To address this issue, we propose an algorithm with a provable approximation ratio of $O\mathsf{}\mathrm{(}\log \mathsf{}k\mathrm{)}$ when only ML constraints are considered. We also empirically evaluate the performance of our algorithm on real-world datasets having artificial ML and disjoint CL constraints. The experimental results show that our algorithm outperforms the existing greedy-based heuristic methods in clustering accuracy.

With the prevalence of big-data technology, intricate, nanoscale Multi-Processor System-on-Chips (MP-SoCs) have been used in various safety-critical applications. However, with no extra countermeasures taken, this widespread use of MP-SoCs can lead to an undesirable decrease in their dependability. This study presents a promising approach using a group of Embedded Instruments (EIs) inside a processor core for health monitoring. Multiple health monitoring datasets obtained from the employed EIs are sampled and collated via the implemented experiment and thereafter used for conducting its remaining useful lifetime prognostics. This enables MP-SoCs to undertake preventive self-repair, thus realizing a zero mean downtime system and ensuring improved dependability. In addition, a principal component analysis based algorithm is designed for realizing the EI data fusion. Subsequently, a genetic algorithm based degradation optimization is employed to create a lifetime prediction model with respect to the processor.

Emerging applications widely use field-programmable gate array (FPGA) prototypes as a tool to verify modern very-large-scale integration (VLSI) circuits, imposing many problems, including routing failure caused by the limited number of connections among blocks of FPGAs therein. Such a shortage of connections can be alleviated through time-division multiplexing (TDM), by which multiple signals sharing an identical routing channel can be transmitted. In this context, the routing quality dominantly decides the performance of such systems, proposing the requirement of minimizing the signal delay between FPGA pairs. This paper proposes algorithms for the routing problem in a multi-FPGA system with TDM support, aiming to minimize the maximum TDM ratio. The algorithm consists of two major stages: (1) A method is proposed to set the weight of an edge according to how many times it is shared by the routing requirements and consequently to compute a set of approximate minimum Steiner trees. (2) A ratio assignment method based on the edge-demand framework is devised for assigning ratios to the edges respecting the TDM ratio constraints. Experiments were conducted against the public benchmarks to evaluate our proposed approach as compared with all published works, and the results manifest that our method achieves a better TDM ratio in comparison.