A polynomial-time approximation scheme for maximizing the minimum machine completion time
From MaRDI portal
Publication:1362519
DOI10.1016/S0167-6377(96)00055-7zbMath0879.90121OpenAlexW2133097277WikidataQ128119066 ScholiaQ128119066MaRDI QIDQ1362519
Publication date: 5 August 1997
Published in: Operations Research Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0167-6377(96)00055-7
Abstract computational complexity for mathematical programming problems (90C60) Deterministic scheduling theory in operations research (90B35)
Related Items (68)
Online-bounded analysis ⋮ Approximation algorithms for simple assembly line balancing problems ⋮ Approximate Maximin Share Allocations in Matroids ⋮ On maximin share allocations in matroids ⋮ Approximation Algorithms for Computing Maximin Share Allocations ⋮ Comparing the minimum completion times of two longest-first scheduling-heuristics ⋮ SEMI-ONLINE MACHINE COVERING ⋮ Allocating indivisible goods to strategic agents: pure Nash equilibria and fairness ⋮ Robust Polynomial-Time Approximation Schemes for Parallel Machine Scheduling with Job Arrivals and Departures ⋮ Optimal preemptive online algorithms for scheduling with known largest size on two uniform machines ⋮ A fast and effective subset sum based improvement procedure for workload balancing on identical parallel machines ⋮ SEMI-ON-LINE SCHEDULING PROBLEM FOR MAXIMIZING THE MINIMUM MACHINE COMPLETION TIME ON THREE SPECIAL UNIFORM MACHINES ⋮ Semi on-line scheduling problem for maximizing the minimum machine completion time on two uniform machines ⋮ Improved approaches to the exact solution of the machine covering problem ⋮ Optimal semi-online algorithms for machine covering ⋮ A Protocol for Cutting Matroids Like Cakes ⋮ Ordinal Maximin Share Approximation for Goods ⋮ A truthful constant approximation for maximizing the minimum load on related machines ⋮ Computing fair and efficient allocations with few utility values ⋮ Reducing price of anarchy of selfish task allocation with more selfishness ⋮ An on-line scheduling problem of parallel machines with common maintenance time ⋮ Approximation with a fixed number of solutions of some multiobjective maximization problems ⋮ Mixed coordination mechanisms for scheduling games on hierarchical machines ⋮ The fair division of hereditary set systems ⋮ Fair and efficient allocation with few agent types, few item types, or small value levels ⋮ Machine covering in the random-order model ⋮ Online max-min fair allocation ⋮ Fair division of indivisible goods: recent progress and open questions ⋮ Envy-free matchings in bipartite graphs and their applications to fair division ⋮ Polynomial-time combinatorial algorithm for general max-min fair allocation ⋮ General max-min fair allocation ⋮ Structural parameters for scheduling with assignment restrictions ⋮ A survey of approximability and inapproximability results for social welfare optimization in multiagent resource allocation ⋮ Fair allocation of indivisible items with conflict graphs ⋮ Parallel machine covering with limited number of preemptions ⋮ An efficient polynomial time approximation scheme for load balancing on uniformly related machines ⋮ Improved bi-criteria approximation schemes for load balancing on unrelated machines with cost constraints ⋮ On-line machine covering on two machines with local migration ⋮ GRAPH ORIENTATION TO MAXIMIZE THE MINIMUM WEIGHTED OUTDEGREE ⋮ Online scheduling with rejection and reordering: exact algorithms for unit size jobs ⋮ Online algorithms with advice for bin packing and scheduling problems ⋮ Symmetry exploitation for online machine covering with bounded migration ⋮ An improved approximation algorithm for maximin shares ⋮ A better semi-online algorithm for \(\mathrm Q3/s_{1} = s_{2}\leq s_{3}/C_{\mathrm{min}}\) with the known largest size ⋮ Maximin share guarantee for goods with positive externalities ⋮ Approximate maximin shares for groups of agents ⋮ Bi-Criteria Approximation Algorithms for Load Balancing on Unrelated Machines with Costs ⋮ Semi-on-line scheduling problems for maximizing the minimum machine completion time ⋮ Online Bounded Analysis ⋮ Tight bounds for bandwidth allocation on two links ⋮ Machine covering with combined partial information ⋮ Optimal on-line algorithms for the uniform machine scheduling problem with ordinal data ⋮ Optimal semi-online preemptive algorithms for machine covering on two uniform machines ⋮ Approximation schemes for scheduling and covering on unrelated machines ⋮ MapReduce machine covering problem on a small number of machines ⋮ Parallel machine scheduling problems with proportionally deteriorating jobs ⋮ A unified view of parallel machine scheduling with interdependent processing rates ⋮ A Unified Approach to Truthful Scheduling on Related Machines ⋮ Computing fair and efficient allocations with few utility values ⋮ Maximizing the Minimum Load for Selfish Agents ⋮ Maximizing the minimum completion time on parallel machines ⋮ The optimal on-line parallel machine scheduling ⋮ Semi-online machine covering for two uniform machines ⋮ Maximizing the minimum load for selfish agents ⋮ In memoriam: Gerhard Woeginger (1964--2022) ⋮ Preemptive machine covering on parallel machines ⋮ The Price of Connectivity in Fair Division ⋮ A new approach for bicriteria partitioning problem
Cites Work
- Unnamed Item
- Bin packing can be solved within 1+epsilon in linear time
- The exact LPT-bound for maximizing the minimum completion time
- Integer Programming with a Fixed Number of Variables
- On a dual version of the one-dimensional bin packing problem
- Scheduling to Maximize the Minimum Processor Finish Time in a Multiprocessor System
- Analysis of Greedy Solutions for a Replacement Part Sequencing Problem
This page was built for publication: A polynomial-time approximation scheme for maximizing the minimum machine completion time
