Emerging　IoT　applications　impose　line　barrier　coverage　(LBC)　tasks　with　min–max　movement　objective　due　to　requirements　of　energy　balance,　fairness,　etc.　In　LBC,　we　are　given　a　line　barrier　and　a　set　of　n　sensors　distributed　on　the　plane.　The　aim　is　to　move　the　sensors　to　fully　cover　the　given　barrier,　such　that　the　maximum　movement　of　the　mobile　sensors　is　minimized　and　hence　the　energy　consumption　of　the　sensors　are　balanced.　This　paper　proposes　an　exact　algorithm　to　optimally　solve　LBC,　which　deserves　a　runtime　On2　compared　favorably　to　the　previous　state-of-art　runtime　On2logn.　The　key　idea　of　the　improvement　is　acceleration-via-approximation:　devise　a　novel　approximation　algorithm　and　then　use　it　to　accelerate　the　calculation　of　optimum　solutions.　Extensive　numerical　experiments　were　carried　out　to　evaluate　the　practical　performance　of　our　algorithm　against　other　baselines,　demonstrating　its　performance　gain　over　the　previous　state-of-art　algorithms.　©　2023　Elsevier　B.V.