A polynomial-time approximation scheme for maximizing the minimum machine completion time
From MaRDI portal
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
Cites work
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- Analysis of Greedy Solutions for a Replacement Part Sequencing Problem
- Bin packing can be solved within 1+epsilon in linear 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
- The exact LPT-bound for maximizing the minimum completion time
Cited in
(79)- Polynomial Approximation Schemes for the Max-Min Allocation Problem under a Grade of Service Provision
- Optimal semi-online preemptive algorithms for machine covering on two uniform machines
- A unified approach to truthful scheduling on related machines
- An improved approximation algorithm for maximin shares
- Maximizing the minimum load for selfish agents
- Preemptive machine covering on parallel machines
- Parallel machine scheduling problems with proportionally deteriorating jobs
- A new approach for bicriteria partitioning problem
- Approximate maximin shares for groups of agents
- Semi-online machine covering for two uniform machines
- Online bounded analysis
- Maximin share guarantee for goods with positive externalities
- Approximate maximin share allocations in matroids
- Reducing price of anarchy of selfish task allocation with more selfishness
- A fast and effective subset sum based improvement procedure for workload balancing on identical parallel machines
- Polynomial time algorithm for minmax scheduling with common due-window and proportional-linear shortening processing times
- An on-line scheduling problem of parallel machines with common maintenance time
- Fair division of indivisible goods: recent progress and open questions
- On maximin share allocations in matroids
- SEMI-ONLINE MACHINE COVERING
- Bi-Criteria Approximation Algorithms for Load Balancing on Unrelated Machines with Costs
- General max-min fair allocation
- Allocating indivisible goods to strategic agents: pure Nash equilibria and fairness
- Mathematical Foundations of Computer Science 2003
- Symmetry exploitation for online machine covering with bounded migration
- Maximizing the Minimum Load for Selfish Agents
- Approximation schemes for the min-max starting time problem
- Improved approaches to the exact solution of the machine covering problem
- Fair allocation of indivisible items with conflict graphs
- Approximation with a fixed number of solutions of some multiobjective maximization problems
- Optimal semi-online algorithms for machine covering
- Online-bounded analysis
- Tight bounds for bandwidth allocation on two links
- Maximizing the minimum completion time on parallel machines
- Online scheduling with rejection and reordering: exact algorithms for unit size jobs
- Optimal preemptive online algorithms for scheduling with known largest size on two uniform machines
- Transforming a pseudo-polynomial algorithm for the single machine total tardiness maximization problem into a polynomial one
- A truthful constant approximation for maximizing the minimum load on related machines
- Comparing the minimum completion times of two longest-first scheduling-heuristics
- Online algorithms with advice for bin packing and scheduling problems
- Machine covering with combined partial information
- SEMI-ON-LINE SCHEDULING PROBLEM FOR MAXIMIZING THE MINIMUM MACHINE COMPLETION TIME ON THREE SPECIAL UNIFORM MACHINES
- On-line machine covering on two machines with local migration
- Approximation algorithms for computing maximin share allocations
- Optimal on-line algorithms for the uniform machine scheduling problem with ordinal data
- A survey of approximability and inapproximability results for social welfare optimization in multiagent resource allocation
- The optimal on-line parallel machine scheduling
- Approximation schemes for scheduling and covering on unrelated machines
- In memoriam: Gerhard Woeginger (1964--2022)
- The fair division of hereditary set systems
- A protocol for cutting matroids like cakes
- A unified view of parallel machine scheduling with interdependent processing rates
- Improved bi-criteria approximation schemes for load balancing on unrelated machines with cost constraints
- Robust polynomial-time approximation schemes for parallel machine scheduling with job arrivals and departures
- A better semi-online algorithm for \(\mathrm Q3/s_{1} = s_{2}\leq s_{3}/C_{\mathrm{min}}\) with the known largest size
- Algorithm for quadratic semi-assignment problem with partition size coefficients
- Computing fair and efficient allocations with few utility values
- Approximation algorithms for simple assembly line balancing problems
- Semi on-line scheduling problem for maximizing the minimum machine completion time on two uniform machines
- The price of connectivity in fair division
- Graph orientation to maximize the minimum weighted outdegree
- Semi-on-line scheduling problems for maximizing the minimum machine completion time
- Strongly Fully Polynomial Time Approximation Scheme for the weighted completion time minimization problem on two-parallel capacitated machines
- Fast fully polynomial approximation schemes for minimizing completion time variance
- Parallel machine covering with limited number of preemptions
- An efficient polynomial time approximation scheme for load balancing on uniformly related machines
- Online max-min fair allocation
- Computing fair and efficient allocations with few utility values
- Polynomial-time combinatorial algorithm for general max-min fair allocation
- MapReduce machine covering problem on a small number of machines
- Mixed coordination mechanisms for scheduling games on hierarchical machines
- Scheduling in manufacturing with transportation: classification and solution techniques
- Machine covering in the random-order model
- Fair and efficient allocation with few agent types, few item types, or small value levels
- An improved approximation scheme for the Johnson problem with parallel machines
- scientific article; zbMATH DE number 781227 (Why is no real title available?)
- Envy-free matchings in bipartite graphs and their applications to fair division
- scientific article; zbMATH DE number 4011924 (Why is no real title available?)
- Ordinal Maximin Share Approximation for Goods
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)
