1. A method for optimizing a partition of a data block into matching and non-matching segments in data deduplication using a processor device in a computing environment, the method comprising: applying an optimal calculation operation in polynomial time to the matching segments for selecting a globally optimal subset of a set of the matching segments according to overhead considerations for minimizing an overall size of a deduplicated file by determining a trade off between a time complexity and a space complexity.