This paper presents a low-cost multiple object tracking (MOT) technique by employing a novel appearance update model for object appearance modeling using K-means. The state-of-the-art work has attained a very high accuracy without considering the real-time aspects necessitated by currently trending embedded vision platforms. The major research on multiple object tracking is used to update the appearance model in every frame while discounting its persistent nature. The proposed appearance update model reduces the computational cost of the state-of-the-art MOT 6-fold by exploiting this facet of persistent appearance over the sequence of frames. To ensure accuracy, the proposed model is tested on different publicly available standard datasets with challenging situations for both indoor and outdoor scenarios. The experimental results illustrate that our model successfully achieves multiple object tracking while coping with long-term and complete occlusion. The proposed method achieves the same accuracy in comparison with the state-of-the-art baseline methods. Moreover, and most importantly, the proposed method is cost-effective in terms of computing and/or memory requirements in comparison to the state-of-the-art techniques. All these traits make our design very suitable for real-time and embedded video surveillance applications with low computing/memory resources.