A Dynamic Cost-Deviation Greedy Algorithm for Large-Scale Assignment Problems

This paper presents the Dynamic Cost-Deviation Greedy Algorithm (DCDGA), a novel algorithmic framework for solving large-scale assignment problems, a class of combinatorial optimization challenges central to theoretical and applied computer science. Unlike the Standard Greedy Algorithm (SGA), which is efficient but often suboptimal, DCDGA integrates a cost-deviation adjustment mechanism, adaptive weighting, and entropy-based prioritization to improve both stability and accuracy. Theoretical analysis demonstrates that DCDGA preserves the asymptotic complexity of the original greedy method (O(n² log n) time, O(n²) space), while offering provable improvements in expected solution cost and robustness under high-variance conditions. Experimental evaluation on synthetic datasets inspired by train scheduling and resource allocation shows that DCDGA achieves, on average, a ~10% reduction in solution cost compared to SGA, with only modest runtime overhead. While SGA occasionally outperforms DCDGA in smaller or low-variance cases, the overall trend indicates that DCDGA is more effective in large-scale, high-complexity problem instances. Comparisons with metaheuristics such as Genetic Algorithms and Simulated Annealing further establish DCDGA’s superior scalability for larger datasets. These findings position DCDGA as a practical, scalable optimization technique applicable to diverse domains including logistics, supply chain management, and network design, contributing to advancing research in algorithms and complexity within computer science