Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(7)
Bin Packing
Bin Packing Problem
Dual Problem
Multiprocessor Scheduling
Scheduling Problem
Knapsack Problem
Multi Dimensional
Related Publications
(5)
Improved Scheduling Algorithms for Minsum Criteria
Resource Constrained Scheduling as Generalized Bin Packing
Vector Assignment Problems: A General Framework
Approximate Algorithms for Some Generalized Knapsack Problems
Approximation algorithms for mdimensional 01 knapsack problem: Worst case and probabilistic analysis
Subscribe
Academic
Publications
On multidimensional packing problems
On multidimensional packing problems,10.1145/314500.314555,Chandra Chekuri,Sanjeev Khanna
Edit
On multidimensional packing problems
(
Citations: 52
)
BibTex

RIS

RefWorks
Download
Chandra Chekuri
,
Sanjeev Khanna
We study the approximability of multidimensional generalizationsof the classical problems of multiprocessor scheduling,bin packing and the knapsack problem. Specifically,we study the vector scheduling problem, its dual problem,namely, the vector
bin packing
problem, and a class of packinginteger programs. The vector
scheduling problem
is toschedule n ddimensional tasks on m machines such that themaximum load over all dimensions and all machines is minimized.The vector bin packing...
Conference:
ACMSIAM Symposium on Discrete Algorithms  SODA
, pp. 185194, 1999
DOI:
10.1145/314500.314555
Cumulative
Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
(
portal.acm.org
)
Citation Context
(29)
...We can show that operator placement to minimize MaceWC is NPhard, by a reduction from vector scheduling [
13
] (our technical report [12] has the details)...
Badrish Chandramouli
,
et al.
Accurate latency estimation in a distributed event processing system
...To address this issue, a number of articles [8,
9
] proposed polynomial time approximate algorithms, but the approximate rate is low...
Liang Shao
,
et al.
Migration in virtual resource management
...The problem of optimally consolidating servers in a data center is often formulated as a variant of the vector binpacking problem [
11
], which is an NPhard optimization problem...
Qi Zhang
,
et al.
Cloud computing: stateoftheart and research challenges
...The first nontrivial result was produced by Chekuri and Khanna [
19
] who gave a polynomialtime algorithm that, for any fixed "> 0, delivers a ð1 þ "d þ Oðlog" � 1 ÞÞapproximate solution...
...As compared to the PTAS described in Chekuri and Khanna [
19
], we also use the results of an LPrelaxation in the first phase, but use an integer program in the second step to find an integral assignment of those services that were fractionally assigned in the LP relaxation...
Benjamin Speitkamp
,
et al.
A Mathematical Programming Approach for Server Consolidation Problems ...
...Vector packing has been studied from both a theoretical standpoint (i.e., guaranteed algorithms) [
44
], [45] and a pragmatic one (i.e., efficient heuristics) [33], [46], [47]...
Mark Stillwell
,
et al.
Dynamic fractional resource scheduling for HPC workloads
References
(32)
Parallel Query Scheduling and Optimization with Time and SpaceShared Resources
(
Citations: 39
)
Minos N. Garofalakis
,
Yannis E. Ioannidis
Conference:
Very Large Data Bases  VLDB
, pp. 296305, 1997
Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
(
Citations: 337
)
Oscar H. Ibarra
,
Chul E. Kim
Journal:
Journal of The ACM  JACM
, vol. 22, no. 4, pp. 463468, 1975
Improved approximations of packing and covering problems
(
Citations: 56
)
Aravind Srinivasan
Conference:
ACM Symposium on Theory of Computing  STOC
, pp. 268276, 1995
A probabilistic analysis of multidimensional bin packing problems
(
Citations: 24
)
Richard M. Karp
,
Michael Luby
,
Alberto MarchettiSpaccamela
Conference:
ACM Symposium on Theory of Computing  STOC
, pp. 289298, 1984
Bounds for Multiprocessor Scheduling with Resource Constraints
(
Citations: 105
)
M. R. Garey
,
Ronald L. Graham
Journal:
Siam Journal on Computing  SIAMCOMP
, vol. 4, no. 2, pp. 187200, 1975
Sort by:
Citations
(52)
Accurate latency estimation in a distributed event processing system
(
Citations: 1
)
Badrish Chandramouli
,
Jonathan Goldstein
,
Roger S. Barga
,
Mirek Riedewald
,
Ivo Santos
Conference:
International Conference on Data Engineering  ICDE
, pp. 255266, 2011
Willow: A Control System for Energy and Thermal Adaptive Computing
Krishna Kant
,
Muthukumar Murugan
,
David H. C. Du
Published in 2011.
Migration in virtual resource management
Liang Shao
,
Yanna Yan
Conference:
International Conference on Consumer Electronics, Communications and Networks  CECNet
, 2011
Cloud computing: stateoftheart and research challenges
(
Citations: 19
)
Qi Zhang
,
Lu Cheng
,
Raouf Boutaba
Journal:
Journal of Internet Services and Applications
, vol. 1, no. 1, pp. 718, 2010
A Mathematical Programming Approach for Server Consolidation Problems in Virtualized Data Centers
(
Citations: 6
)
Benjamin Speitkamp
,
Martin Bichler
Journal:
IEEE Transactions on Services Computing
, vol. 3, no. 4, pp. 266278, 2010