For a positive integer k ≥ 1 , a k -star ( k + -star, k − -star, respectively) is a connected graph containing a degree- ℓ vertex and ℓ degree-1 vertices, where ℓ = k ( ℓ ≥ k , 1 ≤ ℓ ≤ k , respectively). The k + -star packing problem is to cover as many vertices of an input graph G as possible using vertex-disjoint k + -stars in G ; and given k > t ≥ 1 , the k − / t -star packing problem is to cover as many vertices of G as possible using vertex-disjoint k − -stars but no t -stars in G . Both problems are NP-hard for any fixed k ≥ 2 . We present a ( 1 + k 2 2 k + 1 ) - and a 3 2 -approximation algorithms for the k + -star packing problem when k ≥ 3 and k = 2 , respectively, and a ( 1 + 1 t + 1 + 1 / k ) -approximation algorithm for the k − / t -star packing problem when k > t ≥ 2 . They are all local search algorithms and they improve the best known approximation algorithms for the problems, respectively.

This paper studies MPCv5+, which is to cover as many vertices as possible in a given graph G=(V,E) by vertex-disjoint 5+-paths (i.e., paths each with at least five vertices). MPCv5+ is NP-hard and admits an existing local-search-based approximation algorithm which achieves a ratio of [Formula presented] and runs in O(|V|6) time. In this paper, we present a new approximation algorithm for MPCv5+ which achieves a ratio of 2.511 and runs in O(|V|2.5|E|2) time. Unlike the previous algorithm, the new algorithm is based on maximum matching, maximum path-cycle cover, and recursion. © 2025 The Author(s)

Scheduling within a limited budget is closely related to several much studied scheduling with compression and rescheduling problems, and is also a variant of the more recent model of scheduling with testing. In this problem, one seeks to minimize the makespan for a set of jobs that are to be processed on a number of parallel identical machines. Each job J j is given an upper bound u j on its actual processing time p j , and a testing fee c j . In the offline case, the processing time p j is known to the scheduler; while in the oblivious case, p j is revealed to the scheduler only if the testing fee c j is paid. So the scheduler can choose to execute J j on any one of the machines non-preemptively for u j time or pay for the testing and then execute the job for p j time. The scheduler is given a budget B to pay for testing and seeks to minimize the makespan within that budget. The offline problem is denoted as P ∣ u j , p j , c j , B ∣ C max , and the oblivious problem is denoted as P ∣ u j , − , c j , B ∣ C max , where P stands for multiple parallel identical machines with the number of machines being part of the input. We contribute a polynomial-time approximation scheme (PTAS) for the offline problem P ∣ u j , p j , c j , B ∣ C max , which leads to an almost tight ( 2 + ϵ ) -competitive algorithm for the oblivious problem P ∣ u j , − , c j , B ∣ C max .

Conventional low-power system-on-chips (SoCs) commonly regulate digital logic using adaptive voltage and frequency scaling (AVFS), while SRAM voltage is managed by an independent scaling policy. This separation leaves cross-domain SRAM-related critical paths over-margined and prevents system-level energy optimization. This brief presents a unified voltage co-regulation framework that jointly tunes the digital and SRAM supply rails to minimize total SoC energy. A tunable replica oscillator (TRO) is repurposed from a digital timing monitor into a dual-mode delay allocator: its programmable level sets the digital timing slack, and an all-digital AVFS loop adjusts the digital supply to lock the target frequency. The released cycle budget is then converted into SRAM voltage reduction, determined by a cache-based canary test. Domain-level power is profiled on-chip to enable a measurement-driven search for the dual-domain minimum-energy point (DD-MEP) without relying on PVT-dependent model parameters. Silicon results from a taped-out 110-nm Cortex-M3 SoC demonstrate up to 11.4% total energy reduction compared with digital-only AVFS, with only 0.05% area overhead.

We study the fair allocation of indivisible items to n agents to maximize the utilitarian social welfare, where the fairness criterion is envy-free up to one item and there are only two different utility functions shared by the agents. We present a 2-approximation algorithm when the two utility functions are normalized, improving the previous best ratio of 16 √n shown for general normalized utility functions; thus this constant ratio approximation algorithm confirms the APX-completeness in this special case previously shown APX-hard. When there are only three agents, i.e., n = 3, the previous best ratio is 3 shown for general utility functions, and we present an improved and tight 5/3-approximation algorithm when the two utility functions are normalized, and a best possible and tight 2-approximation algorithm when the two utility functions are unnormalized.

Autonomous machines often encounter complex timing constraints, such as those concerning end-to-end timing guarantees and real-time data fusion, etc. Tasks are often event-triggered or time-triggered at varying rates and exhibit data dependencies in between. Maintaining the real-time performance of autonomous machines becomes a highly challenging endeavor. In this paper, we formulate the workload of an autonomous machine as a hybrid Directed Acyclic Graph (DAG), which contains both time-trigger tasks and event-trigger tasks, with a distinct focus on the task of ensuring timing consistency in data fusion and adherence to end-to-end constraints within the DAG model. We design a concise mechanism to select suitable data received by a node and transmit them to successor nodes. This ensures both the timing disparity—as reflected by the differences in timestamps of the data used for fusion—and the end-to-end latency from the sensor to the controller is confined within a certain boundary. The proposed method is proven to be optimal as it always selects suitable data to guarantee the timing correctness of an autonomous machine as far as it (inherently) has the capacity. Experimental results show that our method can significantly improve the success rate of guaranteeing both timing consistency and end-to-end constraints of the autonomous machine.

The problem studied in this paper is to find a collection of vertex-disjoint paths in a given graph G = ( V , E ) such that each path has length at least k , called a long path, and the total number of edges on these paths is maximized. The problem is NP-hard for any fixed k or when k is part of the input, by a reduction from the Hamiltonian path problem. Berman and Karpinski presented a 7/6-approximation algorithm for k = 1 , but for a general k ≥ 2 , there is no approximation algorithm directly for the problem. We present the first local search ( 0.4394 k + O ( 1 ) ) -approximation algorithm for any fixed k ≥ 1 , and a 1.4254-approximation algorithm for k = 2 built on top of a maximum triangle-free path-cycle cover.

We study a variant of the well-known Path Cover problem where the candidate paths in a solution have orders up to a fixed integer k . In Path Cover, one finds a minimum number of vertex-disjoint paths in an input graph to cover all the vertices; in our variant, not all paths but only those short ones, i.e., containing up to k vertices, can be used as candidates. The problem is NP-hard when k ≥ 3 ; in the literature, there exist quite a number of approximation algorithms, especially for small k 's. We present an improved k 3 -approximation algorithm for k ∈ { 6 , 7 , 8 } , an improved 55 31 -approximation algorithm for k = 5 , and an improved 8 5 -approximation algorithm for k = 4 . The novelty inside these improved algorithms is observing a close connection between an optimal path cover and a certain polynomial-time computed edge set.

Given a graph, the general problem to cover the maximum number of vertices by a collection of vertex-disjoint long paths seemingly escapes from the literature. A path containing at least $k$ vertices is considered long. When $k \le 3$, the problem is polynomial time solvable; when $k$ is the total number of vertices, the problem reduces to the Hamiltonian path problem, which is NP-complete. For a fixed $k \ge 4$, the problem is NP-hard and the best known approximation algorithm for the weighted set packing problem implies a $k$-approximation algorithm. To the best of our knowledge, there is no approximation algorithm directly designed for the general problem; when $k = 4$, the problem admits a $4$-approximation algorithm which was presented recently. We propose the first $(0.4394 k + O(1))$-approximation algorithm for the general problem and an improved $2$-approximation algorithm when $k = 4$. Both algorithms are based on local improvement, and their theoretical performance analyses are done via amortization and their practical performance is examined through simulation studies.

Wear-out has been a critical reliability problem in NAND flash memory. As executing repeated program and erase operations on the NAND flash chips, the number of errors increases and ultimately exceeds the ECC capability. In previous work, error characteristics of flash wear-out are observed by endurance tests on a single type of NAND flash memory. We wonder if the experimental results cover the entire error characteristics of NAND flash memory. In this paper, we tested more than 20 types of NAND flash chips with different vendors and structures and presented an overlook of test results. Through the test results, we found an unexpected error-explosion phenomenon that errors of flash blocks first increase over several cycles and then reach a high value without warning. We analyzed the features of the error-explosion and explored its influence on operation time. And we propose an error-explosion prediction scheme to find the blocks that will occur an error-explosion in the next 1000 P/E cycles. The block identifying operation is realized by the machine-learning model. The performance of six machine-learning methods is compared. The results demonstrate that the Decision Trees and Bagged Classification Trees have the best accuracy.

In Solid State Drives, flash management techniques such as wear-leveling and refresh usually assume NAND flash memories have the same endurance value. However, the actual endurance values differ from blocks to blocks. This reliability difference is introduced by process-variation during flash fabrication. In recent years, for improving flash management techniques, various works have been done on the reliability variation of 2D flash memory. As 2D NAND transmitted to 3D NAND flash, the vertical structure and multi-layer stacking changed the effect of previously known reliability problems. In this paper, we are first to characterize the process-variation effects on 3D TLC flash reliability. The characterization includes two parts: endurance variation and error feature variation. Second, we propose an adaptive error prediction scheme to mitigate the process-variation effects. This scheme uses the machine-learning model to realize the error prediction operation. We also discuss the implications of this scheme on main flash management techniques.