Real time asymptotic packing
type: Item
instance of: scholarly article
title: Real time asymptotic packing
zbMATH Open document ID: 0884.05031
published in: The Electronic Journal of Combinatorics
publication date: 1998-02-15T00:00:00Z
full work available at URL: https://eudml.org/doc/119215
full work available at URL: v4i2r19ab.html
review text: Summary: A random greedy algorithm, somewhat modified, is analyzed by using a real time context and showing that the variables remain close to the solution of a natural differential equation. Given a \((k+1)\)-uniform simple hypergraph on \(N\) vertices, regular of degree \(D\), the algorithm gives a packing of disjoint hyperedges containing all but \(O(ND^{-1/k}\ln^cD)\) of the vertices.
Mathematics Subject Classification ID: 05B40
Mathematics Subject Classification ID: 60D05
Mathematics Subject Classification ID: 05C65
zbMATH DE Number: 1118075
zbMATH Keywords: random greedy algorithm
zbMATH Keywords: differential equation
zbMATH Keywords: hypergraph
zbMATH Keywords: packing
author: Joel Spencer
MaRDI profile type: Publication
Recommended article: Computational Science and Its Applications – ICCSA 2004
Recommended article: Q4885222
Recommended article: Q4967203
Recommended article: Parameterized approximation algorithms for packing problems
Recommended article: Q5501258
Recommended article: Efficient algorithms for real-life instances of the variable size bin packing problem
Recommended article: Optimized packings with applications
Recommended article: On packing time-respecting arborescences
Recommended article: Bin packing: Asymptotically exact approach
description: scientific article; zbMATH DE number 1118075