Minimizing makespan in sublinear time via weighted random sampling

DOI10.1007/978-3-032-27732-9_37MaRDI QIDQ7363411zbMATH OpenFDO

Authors Bin Fu, Yumei Huo, Hairong Zhao

Publication date 29 September 2026

Full work available at URL https://doi.org/10.1007/978-3-032-27732-9_37

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68Rxx) Algorithms in computer science (68Wxx)

Cites work

• A sublinear-time approximation scheme for bin packing
• An EPTAS for scheduling jobs on uniform processors: using an MILP relaxation with a constant number of integral variables
• Better sum estimation via weighted sampling
• Bin packing with restricted piece sizes
• Bounds for Certain Multiprocessing Anomalies
• Bounds on Multiprocessing Timing Anomalies
• Closing the gap for makespan scheduling via sparsification techniques
• Estimating Sum by Weighted Sampling
• Estimating the weight of metric minimum spanning trees in sublinear-time
• Exact and Approximate Algorithms for Scheduling Nonidentical Processors
• On Sums of Independent Random Variables with Unbounded Variance and Estimating the Average Degree in a Graph
• Property testing and its connection to learning and approximation
• Scheduling Semiconductor Burn-In Operations to Minimize Total Flowtime
• Sublinear Geometric Algorithms
• Sublinear time algorithms and complexity of approximate maximum matching
• Sublinear time approximation schemes for makespan minimization on parallel machines
• Sublinear time width-bounded separators and their application to the protein side-chain packing problem
• Time-optimal sublinear algorithms for matching and vertex cover

This page was built for publication: Minimizing makespan in sublinear time via weighted random sampling

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7363411)