Combinatorics, Algorithms, Probabilistic and Experimental Methodologies: First International Symposium, ESCAPE 2007, Hangzhou, China, April 7-9, 2007, Revised Selected Papers
The refereed post-proceedings of the First International Symposium on Combinatorics, Algorithms, Probabilistic and Experimental Methodologies are presented in this volume. The symposium provided an interdisciplinary forum for researchers to share their discoveries and approaches. The 46 full papers address large data processing problems using different methodologies from major disciplines such as computer science, combinatorics, and statistics.
6.10. rezultāts no 60.
Let us denote the optimal bins as B; for i = 1,..., OPT(I), and the FFD bins as B; for i = 1,..., FFD(I). The sum of the sizes of items being packed into a bin will be denoted as Y (B.), and Y (B.), respectively.
We say that bin Bi dominates j, if for every item yk being the optimal bin B∗j for some i and in B∗j there exists an item yl being in Bi for which yk ≤ yl and ... There are no bins Bi and B∗j dominates B∗j. such that Bi Proof.
For the value of optimum bins holds that OPT(I) ≥ 6, and in case X ≤ 1/5 a stronger inequality OPT(I) ≥ 10 also holds. Proof. ... We call a bin as open bin if there is at least one item already packed into the bin. A bin is closed if ...
This is packed by FFD into an earlier bin, which contains exactly one more item L ≥ L > 1/2. Then decrease the size of this item to be equal to xi. Then it will be packed into the same bin, and there will no more item be packed into ...
We denote the weight of an item Z as w(Z), and the weight of an optimal or FFD bin as w(B∗), or w(B), respectively. ... i.e. the reserve of all optimal bins are nonnegative, and almost all of the optimal bins have positive reserve.
Lietotāju komentāri - Rakstīt atsauksmi
A Deterministic Summary Structure for Update Data Streams
An Effective Refinement Algorithm Based on Swarm Intelligence for Graph Bipartitioning
On the Complexity and Approximation of the MinSum and MinMax Disjoint Paths Problems
A Digital Watermarking Scheme Based on Singular Value Decomposition
Fast Matching Method for DNA Sequences
AllPairs Ancestor Problems in Weighted Dags
Streaming Algorithms for Data in Motion
A Scheduling Problem with One Producer and the Bargaining Counterpart with Two Producers
PhraseBased Statistical Language Modeling from Bilingual Parallel Corpus
Optimal Commodity Distribution for a Vehicle with Fixed Capacity Under Vendor Managed Inventory
OnLine Bin Packing with Arbitrary Release Times
On the Complexity of the MaxEdgeColoring Problem with Its Variants
A New t nThreshold Scheme Based on Difference Equations
CliqueTransversal Sets in Cubic Graphs
On the Lh kLabeling of Cocomparability Graphs
An Approximation Algorithm for the General Mixed Packing and Covering Problem
Extending the Hardness of RNA Secondary Structure Comparison
On the OnLine Weighted kTaxi Problem
Model Futility and Dynamic Boundaries with Application in Banking Default Risk Modeling
On the Minimum RiskSum Path Problem
Constrained Cycle Covers in Halin Graphs
Optimal Semionline Algorithms for Scheduling with Machine Activation Cost
A Fast Asymptotic Approximation Scheme for Bin Packing with Rejection
Online Coupon Consumption Problem
Application of Copula and CopulaCVaR in the Multivariate Portfolio Optimization
Online Capacitated Interval Coloring
Energy Efficient Heuristic Scheduling Algorithms for Multimedia Service
Call Control and Routing in SONET Rings
Quantitative Analysis of Multihop Wireless Networks Using a Novel Paradigm
Inverse MinMax Spanning Tree Problem Under the Weighted SumType Hamming Distance
Robust Optimization Model for a Class of Uncertain Linear Programs
An Efficient Algorithm for Solving the Container Loading Problem
A Bijective Code for kTrees with Linear Time Encoding and Decoding
MarketBased Service Selection Framework in Grid Computing
Informative Gene Selection and Tumor Classification by Null Space LDA for Microarray Data
Heuristic Search for 2D NMR Alignment to Support Metabolite Identification
A New Succinct Representation of RMQInformation and Improvements in the Enhanced Suffix Array
Lagrangian Relaxation and Cutting Planes for the Vertex Separator Problem
Finding Pure Nash Equilibrium of Graphical Game Via Constraints Satisfaction Approach
A New Load Balanced Routing Algorithm for Torus Networks
Optimal Semionline Scheduling Algorithms on aSmall Number of Machines
Lower Bounds on Edge Searching