A polynomial-time approximation scheme for maximizing the minimum machine completion time
From MaRDI portal
Publication:1362519
DOI10.1016/S0167-6377(96)00055-7zbMATH Open0879.90121OpenAlexW2133097277WikidataQ128119066 ScholiaQ128119066MaRDI QIDQ1362519FDOQ1362519
Authors: Gerhard J. Woeginger 
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
Recommendations
- Maximizing the minimum completion time on parallel machines
- Approximability of single machine scheduling with fixed jobs to minimize total completion time
- A faster fully polynomial approximation scheme for the single-machine total tardiness problem
- A fully polynomial-time approximation scheme for total completion time minimization on a single machine with DeJong's learning effect and an availability constraint
- Strongly Fully Polynomial Time Approximation Scheme for the weighted completion time minimization problem on two-parallel capacitated machines
- Minimizing total completion time on uniform machines with deadline constraints
- Polynomial time approximation algorithms for machine scheduling: Ten open problems
- A fully polynomial time approximation scheme for makespan minimization problems on two machines with a fixed non-availability interval
- Minimizing total completion time and maximum cost simultaneously is solvable in polynomial time
- Combinatorial algorithms for minimizing the weighted sum of completion times on a single machine
Deterministic scheduling theory in operations research (90B35) Abstract computational complexity for mathematical programming problems (90C60)
Cites Work
- Title not available (Why is that?)
- On a dual version of the one-dimensional bin packing problem
- Bin packing can be solved within 1+epsilon in linear time
- Integer Programming with a Fixed Number of Variables
- The exact LPT-bound for maximizing the minimum completion time
- Scheduling to Maximize the Minimum Processor Finish Time in a Multiprocessor System
- Analysis of Greedy Solutions for a Replacement Part Sequencing Problem
Cited In (80)
- Mixed coordination mechanisms for scheduling games on hierarchical machines
- Ordinal Maximin Share Approximation for Goods
- An improved approximation scheme for the Johnson problem with parallel machines
- Scheduling in manufacturing with transportation: classification and solution techniques
- Envy-free matchings in bipartite graphs and their applications to fair division
- Polynomial-time combinatorial algorithm for general max-min fair allocation
- Online max-min fair allocation
- MapReduce machine covering problem on a small number of machines
- Fair and efficient allocation with few agent types, few item types, or small value levels
- Machine covering in the random-order model
- Computing fair and efficient allocations with few utility values
- Title not available (Why is that?)
- Title not available (Why is that?)
- 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
- Semi on-line scheduling problem for maximizing the minimum machine completion time on two uniform machines
- Maximin share guarantee for goods with positive externalities
- A unified view of parallel machine scheduling with interdependent processing rates
- Maximizing the minimum load for selfish agents
- Online algorithms with advice for bin packing and scheduling problems
- Machine covering with combined partial information
- Mathematical Foundations of Computer Science 2003
- Online-bounded analysis
- Symmetry exploitation for online machine covering with bounded migration
- Optimal preemptive online algorithms for scheduling with known largest size on two uniform machines
- Approximation algorithms for simple assembly line balancing problems
- Optimal semi-online preemptive algorithms for machine covering on two uniform machines
- On maximin share allocations in matroids
- Optimal on-line algorithms for the uniform machine scheduling problem with ordinal data
- Robust polynomial-time approximation schemes for parallel machine scheduling with job arrivals and departures
- Semi-on-line scheduling problems for maximizing the minimum machine completion time
- A protocol for cutting matroids like cakes
- Approximate maximin share allocations in matroids
- Transforming a pseudo-polynomial algorithm for the single machine total tardiness maximization problem into a polynomial one
- Fast fully polynomial approximation schemes for minimizing completion time variance
- General max-min fair allocation
- Comparing the minimum completion times of two longest-first scheduling-heuristics
- Graph orientation to maximize the minimum weighted outdegree
- Approximation schemes for the min-max starting time problem
- Improved bi-criteria approximation schemes for load balancing on unrelated machines with cost constraints
- Computing fair and efficient allocations with few utility values
- Polynomial Approximation Schemes for the Max-Min Allocation Problem under a Grade of Service Provision
- Improved approaches to the exact solution of the machine covering problem
- Approximation schemes for scheduling and covering on unrelated machines
- Strongly Fully Polynomial Time Approximation Scheme for the weighted completion time minimization problem on two-parallel capacitated machines
- SEMI-ONLINE MACHINE COVERING
- Optimal semi-online algorithms for machine covering
- In memoriam: Gerhard Woeginger (1964--2022)
- Parallel machine covering with limited number of preemptions
- An efficient polynomial time approximation scheme for load balancing on uniformly related machines
- The fair division of hereditary set systems
- An improved approximation algorithm for maximin shares
- Maximizing the minimum completion time on parallel machines
- Approximation algorithms for computing maximin share allocations
- A unified approach to truthful scheduling on related machines
- Online bounded analysis
- Semi-online machine covering for two uniform machines
- Structural parameters for scheduling with assignment restrictions
- A fast and effective subset sum based improvement procedure for workload balancing on identical parallel machines
- Parallel machine scheduling problems with proportionally deteriorating jobs
- A new approach for bicriteria partitioning problem
- Approximate maximin shares for groups of agents
- Polynomial time algorithm for minmax scheduling with common due-window and proportional-linear shortening processing times
- Online scheduling with rejection and reordering: exact algorithms for unit size jobs
- Fair division of indivisible goods: recent progress and open questions
- Bi-Criteria Approximation Algorithms for Load Balancing on Unrelated Machines with Costs
- SEMI-ON-LINE SCHEDULING PROBLEM FOR MAXIMIZING THE MINIMUM MACHINE COMPLETION TIME ON THREE SPECIAL UNIFORM MACHINES
- The optimal on-line parallel machine scheduling
- Allocating indivisible goods to strategic agents: pure Nash equilibria and fairness
- Fair allocation of indivisible items with conflict graphs
- On-line machine covering on two machines with local migration
- A better semi-online algorithm for \(\mathrm Q3/s_{1} = s_{2}\leq s_{3}/C_{\mathrm{min}}\) with the known largest size
- A survey of approximability and inapproximability results for social welfare optimization in multiagent resource allocation
- The price of connectivity in fair division
- Maximizing the Minimum Load for Selfish Agents
- Tight bounds for bandwidth allocation on two links
- A truthful constant approximation for maximizing the minimum load on related machines
- Preemptive machine covering on parallel machines
- Algorithm for quadratic semi-assignment problem with partition size coefficients
This page was built for publication: A polynomial-time approximation scheme for maximizing the minimum machine completion time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1362519)
