Skip to main content

Fractional Optimization

Learn Fractional Optimization (Greedy Algorithms, Data Structures & Algorithms) with worked examples, diagrams and interview questions. Free on JavaSchoolLab.

Minimizing Average Waiting Time - the General Ratio-Greedy Pattern A whole family of problems is solved by sorting on the RIGHT ratio or simple key, not by anything complex. Classic example: given job durations, schedule them (one at a time, no preemption) to minimize AVERAGE waiting time across all jobs. Greedy answer: run the SHORTEST job first - "Shortest Job First" scheduling.

More lessons in Greedy Algorithms