An approximation algorithm for the generalized assignment problem
From MaRDI portal
Publication:1319018
DOI10.1007/BF01585178zbMath0804.90077WikidataQ56519775 ScholiaQ56519775MaRDI QIDQ1319018
Publication date: 19 January 1995
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
generalized assignment problemparallel machinespolynomial-time algorithmapproximation algorithmsmean job completion time
Related Items
Multiple subset sum with inclusive assignment set restrictions ⋮ EPTAS for the dual of splittable bin packing with cardinality constraint ⋮ Configuration balancing for stochastic requests ⋮ A Survey of the Generalized Assignment Problem and Its Applications ⋮ Reallocation problems with minimum completion time ⋮ Bi-Criteria Approximation Algorithms for Load Balancing on Unrelated Machines with Costs ⋮ Improved Lower Bounds for Non-utilitarian Truthfulness ⋮ A PTAS for Scheduling Unrelated Machines of Few Different Types ⋮ Robustly assigning unstable items ⋮ Unnamed Item ⋮ Vertex cover meets scheduling ⋮ Data migration on parallel disks: Algorithms and evaluation ⋮ Truthful mechanism design for multidimensional scheduling via cycle monotonicity ⋮ Approximation schemes for parallel machine scheduling problems with controllable processing times ⋮ Fast approximation algorithms for bi-criteria scheduling with machine assignment costs ⋮ New approximation algorithms for the unsplittable capacitated facility location problem ⋮ A faster combinatorial approximation algorithm for scheduling unrelated parallel machines ⋮ On some special cases of the restricted assignment problem ⋮ Energy-Efficient Algorithms for Non-preemptive Speed-Scaling ⋮ Polynomial time approximation schemes for class-constrained packing problems ⋮ An efficient approximation for the generalized assignment problem ⋮ Preclustering algorithms for imprecise points ⋮ On dependent randomized rounding algorithms ⋮ A survey of scheduling with controllable processing times ⋮ Truthfulness in advertising? Approximation mechanisms for knapsack bidders ⋮ On the existence of schedules that are near-optimal for both makespan and total weighted completion time ⋮ Bifactor approximation for location routing with vehicle and facility capacities ⋮ Machine scheduling with resource dependent processing times ⋮ Lower and upper bounds for the non-linear generalized assignment problem ⋮ Approximability of Two Variants of Multiple Knapsack Problems ⋮ A survey on offline scheduling with rejection ⋮ Technical Note—The Multinomial Logit Model with Sequential Offerings: Algorithmic Frameworks for Product Recommendation Displays ⋮ A 3/2-approximation algorithm for \(k_i\)-partitioning ⋮ Scheduling and fixed-parameter tractability ⋮ On the configuration LP for maximum budgeted allocation ⋮ Coupled and \(k\)-sided placements: generalizing generalized assignment ⋮ Geometric rounding: A dependent randomized rounding scheme ⋮ Approximation algorithms for the graph balancing problem with two speeds and two job lengths ⋮ Penalty cost constrained identical parallel machine scheduling problem ⋮ Improved lower bounds for non-utilitarian truthfulness ⋮ Maximizing throughput in queueing networks with limited flexibility ⋮ Approximation algorithms for the generalized incremental knapsack problem ⋮ Submodular optimization problems and greedy strategies: a survey ⋮ The equilibrium generalized assignment problem and genetic algorithm ⋮ Improved approximation algorithms for data migration ⋮ Scheduling jobs with sizes and delivery times on identical parallel batch machines ⋮ Assigning real-time tasks to heterogeneous processors by applying ant colony optimization ⋮ Distributed approximation of cellular coverage ⋮ Efficient time-stepping techniques for simulating turbulent reactive flows with stiff chemistry ⋮ Tight Approximation Bounds for the Seminar Assignment Problem ⋮ Two heuristic solution concepts for the vehicle selection problem in line haul transports ⋮ Assigning papers to referees ⋮ On the approximate tradeoff for bicriteria batching and parallel machine scheduling problems. ⋮ Improved bi-criteria approximation schemes for load balancing on unrelated machines with cost constraints ⋮ Generalized assignment problem: truthful mechanism design without money ⋮ Grouping techniques for scheduling problems: simpler and faster ⋮ Monotonizing linear programs with up to two nonzeroes per column ⋮ Mixed integer programming model for scheduling in unrelated parallel processor system with priority consideration ⋮ LP-based approximation algorithms for capacitated facility location ⋮ Distributed approximation of \(k\)-service assignment ⋮ A Family of Scheduling Algorithms for Hybrid Parallel Platforms ⋮ A best first search exact algorithm for the multiple-choice multidimensional knapsack problem ⋮ Single-machine scheduling with machine unavailability periods and resource dependent processing times ⋮ Scheduling to minimize total weighted completion time: Performance guarantees of LP-based heuristics and lower bounds ⋮ Improved approximation algorithms for parallel machine scheduling with release dates and job rejection ⋮ How unsplittable-flow-covering helps scheduling with job-dependent cost functions ⋮ Estimating the makespan of the two-valued restricted assignment problem ⋮ Truthful mechanism design via correlated tree rounding ⋮ The generalized maximum coverage problem ⋮ Non-identical parallel-machine scheduling research with minimizing total weighted completion times: models, relaxations and algorithms ⋮ Approximation schemes for job shop scheduling problems with controllable processing times ⋮ Best compromise solution for a new multiobjective scheduling problem ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The constrained minimum weighted sum of job completion times problem ⋮ A \((1-1/e)\)-approximation algorithm for the generalized assignment problem ⋮ Approximation schemes for scheduling and covering on unrelated machines ⋮ On the approximability of the two-phase knapsack problem ⋮ Iterated greedy local search methods for unrelated parallel machine scheduling ⋮ ILP models for the allocation of recurrent workloads upon heterogeneous multiprocessors ⋮ Performance bounds with curvature for batched greedy optimization ⋮ APPLICATION PLACEMENT ON A CLUSTER OF SERVERS ⋮ Algorithms for hierarchical and semi-partitioned parallel scheduling ⋮ Flexible allocation on related machines with assignment restrictions ⋮ Simpler and Better Algorithms for Minimum-Norm Load Balancing ⋮ Approximate algorithms for unrelated machine scheduling to minimize makespan ⋮ Bandwidth-constrained allocation in grid computing ⋮ Geometric quadrisection in linear time, with application to VLSI placement ⋮ Matrix columns allocation problems ⋮ Two-Agent Advertisement Scheduling on Physical Books to Maximize the Total Profit ⋮ A new Lagrangian Relaxation Algorithm for scheduling dissimilar parallel machines with release dates ⋮ Stochastic Load Balancing on Unrelated Machines ⋮ Scheduling jobs with time-resource tradeoff via nonlinear programming ⋮ Scheduling MapReduce jobs on identical and unrelated processors ⋮ Minimum-cost single-source 2-splittable flow ⋮ Minimizing machine assignment costs over \(\Delta\)-approximate solutions of the scheduling problem \(P||C_{\max}\) ⋮ A polynomial-time approximation scheme for the airplane refueling problem ⋮ Truthful Generalized Assignments via Stable Matching ⋮ An ejection chain approach for the generalized assignment problem ⋮ Concentration inequalities for nonlinear matroid intersection ⋮ Preemptive and non-preemptive scheduling on two unrelated parallel machines ⋮ On dependent randomized rounding algorithms ⋮ Priority algorithms for makespan minimization in the subset model. ⋮ Packing items into several bins facilitates approximating the separable assignment problem ⋮ Minimum-Cost Single-Source 2-Splittable Flow ⋮ Task swapping networks in distributed systems ⋮ The generalized assignment problem with minimum quantities ⋮ A constant-factor approximation algorithm for the \(k\)-median problem ⋮ Maximum coverage with cluster constraints: an LP-based approximation technique ⋮ Generalized fuzzy assignment problem with restriction on the cost of job under hesitant fuzzy environment
Cites Work
- Approximation algorithms for scheduling unrelated parallel machines
- Matching theory
- Scheduling Multiple Variable-Speed Machines
- Scheduling independent tasks to reduce mean finishing time
- Fast Approximation Algorithms for Fractional Packing and Covering Problems
- Technical Note—Minimizing Average Flow Time with Parallel Machines
