Using dual approximation algorithms for scheduling problems: Theoretical and practical results

No abstract is available for this paper.

• Publication year

  1985

• Venue

  26th Annual Symposium on Foundations of Computer Science (sfcs 1985)

• Publication date

  1985-10-21

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1145/7531.7535
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• A packing problem you can almost solve by sitting on your suitcase

  1986cited by this paper
• Tighter Bounds for the Multifit Processor Scheduling Algorithm

  1984cited by this paper
• An efficient approximation scheme for the one-dimensional bin-packing problem

  1982cited by this paper
• The NP-Completeness Column: An Ongoing Guide

  1982cited by this paper
• Bin packing can be solved within 1 + ε in linear time

  1981cited by this paper
• Processor scheduling with improved heuristic algorithms

  1981cited by this paper
• Computers and Intractability: A Guide to the Theory of NP-Completeness

  1979cited by this paper
• Computers and In stractability: A Guide to the Theory of NP-Completeness. W. H Freeman, San Fran

  1979cited by this paper
• Johnson: computers and intractability: a guide to the theory of np- completeness (freeman

  1979cited by this paper
• An Application of Bin-Packing to Multiprocessor Scheduling

  1978cited by this paper
• Sensitivity Analysis for Heuristic Algorithms

  1978cited by this paper
• Fast approximation algorithms for knapsack problems

  1977cited by this paper
• Algorithms for Scheduling Independent Tasks

  1976cited by this paper
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems

  1975cited by this paper
• Bounds on Multiprocessing Timing Anomalies

  1969cited by this paper
• Bounds for certain multiprocessing anomalies

  1966cited by this paper
• Journal of the Association for Computing Machinery

  1961cited by this paper

• Approximation algorithms for demand-based job scheduling with reconfigurable resources

  2026cites this paper
• Integrated operating room scheduling and surgical instrument inventory management: Models, algorithms, and cost-saving insights

  2026cites this paper
• A Practical 73/50 Approximation for Contiguous Monotone Moldable Job Scheduling

  2026cites this paper
• Maximin Shares with Lower Quotas

  2026cites this paper
• Multiple parallel-batch machines scheduling with additive resource assignment and machine available times

  2026cites this paper
• Minimizing Makespan in Sublinear Time via Weighted Random Sampling

  2026cites this paper
• The overflowing bin packing problem: theoretical results and compact ILP formulations

  2026cites this paper
• Two-agent single batch machine scheduling with a fixed capacity distribution

  2026cites this paper
• Sublinear time approximation schemes for makespan minimization on parallel machines

  2025cites this paper
• Robust Task Allocations by Distributing the Risk Among Agents: Theory and Algorithms

  2025cites this paper
• Scheduling moldable tasks on homogeneous multi-cluster platforms with GPUs

  2025cites this paper
• Improved approximation algorithms for multiprocessor indivisible coflow scheduling

  2025influential citation
• Approximation Schemes for k-Subset Sum Ratio and k-Way Number Partitioning Ratio

  2025cites this paper
• An EPTAS for Minimizing the Total Weighted Completion Time of Jobs with Release Dates on Uniformly Related Machines

  2025cites this paper
• Scheduling on Identical Machines with Setup Time and Unknown Execution Time

  2025cites this paper
• Near-Linear Time Scheduling for Drone-Based Parcel Delivery from a Warehouse

  2025cites this paper
• A $(4/3+\varepsilon)$-Approximation for Preemptive Scheduling with Batch Setup Times

  2025cites this paper
• Faster EPTAS for Scheduling on Uniform Machines

  2025cites this paper
• Parallel Machine Scheduling With Periodic Availability Constraints to Minimize Makespan

  2025cites this paper
• Approximation Schemes for k-Subset Sum Ratio and Multiway Number Partitioning Ratio

  2025cites this paper
• Two-stage flexible flow shop scheduling in GPU systems

  2025cites this paper
• Smoothed analysis of the k-swap neighborhood for makespan scheduling

  2025cites this paper
• Efficient $\varepsilon$-approximate minimum-entropy couplings

  2025cites this paper
• An Efficient Polynomial Time Approximation Scheme for Minimizing the Total Weighted Completion Time on Uniformly Related Machines

  2025cites this paper
• Approximation algorithms for scheduling with rejection in green manufacturing

  2025influential citation
• Near-Optimal Cache Sharing through Co-Located Parallel Scheduling of Threads

  2025cites this paper
• A generalized combination of parallel machine scheduling and path

  2024cites this paper
• A probabilistic analysis on general probabilistic scheduling problems

  2024cites this paper
• Two Results on LPT: A Near-Linear Time Algorithm and Parcel Delivery using Drones

  2024cites this paper
• A k-swap Local Search for Makespan Scheduling

  2024cites this paper
• Learning-Augmented Energy-Aware List Scheduling for Precedence-Constrained Tasks

  2024cites this paper
• Load Balancing and Generalized Split State Reconciliation in Event Driven Systems

  2024cites this paper
• Tight Bounds for Online Balanced Partitioning in the Generalized Learning Model

  2024cites this paper
• Computing with oscillators from theoretical underpinnings to applications and demonstrators

  2024cites this paper
• Comparison of adaptive mesh refinement techniques for numerical weather prediction

  2024cites this paper
• A polynomial-time approximation scheme for an arbitrary number of parallel identical multi-stage flow-shops

  2024cites this paper
• Efficient approximation schemes for scheduling on a stochastic number of machines

  2024cites this paper
• The prize-collecting single machine scheduling with bounds and penalties

  2024cites this paper
• Randomized approximation schemes for minimizing the weighted makespan on identical parallel machines

  2024cites this paper
• Hardness and Tight Approximations of Demand Strip Packing

  2024cites this paper
• 3/2-Dual Approximation for CPU/GPU Scheduling

  2024influential citation
• On scheduling multiple parallel two-stage flowshops with Johnson’s Rule

  2024cites this paper
• Scheduling on a Stochastic Number of Machines

  2024cites this paper
• Improved Maximin Share Approximations for Chores by Bin Packing

  2024cites this paper
• Approximation algorithms for scheduling monotonic moldable tasks on multiple platforms

  2023cites this paper
• Approximation algorithms for Job Scheduling with reconfigurable resources

  2023cites this paper
• Polylog-Competitive Algorithms for Dynamic Balanced Graph Partitioning for Ring Demands

  2023cites this paper
• Algorithms for single machine scheduling problem with release dates and submodular penalties

  2023cites this paper
• Scheduling with cardinality dependent unavailability periods

  2023cites this paper
• Practical Performance Guarantees for Pipelined DNN Inference

  2023influential citation
• Exact algorithms for solving the constrained parallel-machine scheduling problems with divisible processing times and penalties

  2023cites this paper
• On the complexity of scheduling unrelated parallel machines with limited preemptions

  2023cites this paper
• A Reduction from Chores Allocation to Job Scheduling

  2023cites this paper
• Scheduling games with rank-based utilities

  2023cites this paper
• A Heuristic Mixed Real-time Task Allocation of Virtual Utilization in Multi-core Processor⋆

  2023cites this paper
• Santa Claus meets Makespan and Matroids: Algorithms and Reductions

  2023cites this paper
• A Survey on Fair Allocation of Chores

  2023cites this paper
• Ordinal Maximin Share Approximation for Chores

  2022cites this paper
• Streaming Algorithms for Multitasking Scheduling with Shared Processing

  2022cites this paper
• (In-)Approximability Results for Interval, Resource Restricted, and Low Rank Scheduling

  2022cites this paper
• An improved approximation algorithm for scheduling monotonic moldable tasks

  2022cites this paper
• A Linearithmic Time Locally Optimal Algorithm for the Multiway Number Partition Optimization

  2022cites this paper
• Tight running times for minimum ℓq-norm load balancing: beyond exponential dependencies on 1/∊

  2022cites this paper
• Starting time minimization for the maximum job variant

  2022cites this paper
• High-multiplicity N-fold IP via configuration LP

  2022cites this paper
• Approximate Dynamic Balanced Graph Partitioning

  2022cites this paper
• Scheduling with Many Shared Resources

  2022cites this paper
• Runtime and energy constrained work scheduling for heterogeneous systems

  2022cites this paper
• An efficient polynomial-time approximation scheme for parallel multi-stage open shops

  2022cites this paper
• Multitasking scheduling with shared processing

  2022influential citation
• Out-of-order backprop: an effective scheduling technique for deep learning

  2022cites this paper
• EPTAS for the dual of splittable bin packing with cardinality constraint

  2022cites this paper
• An analytical performance model of generalized hierarchical scheduling

  2022cites this paper
• Smoothed Online Combinatorial Optimization Using Imperfect Predictions

  2022cites this paper
• Runtime Performance of Evolutionary Algorithms for the Chance-constrained Makespan Scheduling Problem

  2022cites this paper
• Mathematical Modelling and Methods for Load Balancing and Coordination of Multi-Robot Stations

  2022cites this paper
• Tractable Fragments of the Maximum Nash Welfare Problem

  2021cites this paper
• Almost Optimal Inapproximability of Multidimensional Packing Problems

  2021cites this paper
• A Combinatorial 2-Approximation Algorithm for the Parallel-Machine Scheduling with Release Times and Submodular Penalties

  2021cites this paper
• Kernelization of Maximum Minimal Vertex Cover

  2021cites this paper
• A New Framework for Kernelization Lower Bounds: The Case of Maximum Minimal Vertex Cover

  2021cites this paper
• Parameterized complexity of configuration integer programs

  2021cites this paper
• Empowering the configuration-IP: new PTAS results for scheduling with setup times

  2021cites this paper
• EPTAS for parallel identical machine scheduling with time restrictions

  2021influential citation
• Assigning and Scheduling Generalized Malleable Jobs under Submodular Processing Speeds

  2021cites this paper
• Introducing lop-Kernels: A Framework for Kernelization Lower Bounds

  2021cites this paper
• Machine Covering in the Random-Order Model

  2021cites this paper
• Single Machine Vector Scheduling with General Penalties

  2021cites this paper
• A statistical perspective on non-deterministic polynomial-time hard ordering problems: Making use of design for order-of-addition experiments

  2021cites this paper
• Scheduling with Machine Conflicts

  2021cites this paper
• Scheduling with Contact Restrictions - A Problem Arising in Pandemics

  2021cites this paper
• A log-linear (2+5/6)-approximation algorithm for parallel machine scheduling with a single orthogonal resource

  2021cites this paper
• Load Balancing: The Long Road from Theory to Practice

  2021cites this paper
• Online Makespan Minimization with Budgeted Uncertainty

  2021cites this paper
• Approximation algorithms for simple assembly line balancing problems

  2021cites this paper
• EPTAS for load balancing problem on parallel machines with a non-renewable resource

  2021cites this paper
• Closing the gap for single resource constraint scheduling

  2021cites this paper
• Tight running times for minimum $\ell_q$-norm load balancing: beyond exponential dependencies on $1/\epsilon$

  2021cites this paper
• Teaching Complex Scheduling Algorithms

  2021cites this paper
• Decomposing a graph into subgraphs with small components

  2021cites this paper