Random-order online independent set of intervals and hyperrectangles
From MaRDI portal
Cites work
- A 3-approximation algorithm for maximum independent set of rectangles
- A polynomial-time \(\mathrm{OPT}^\varepsilon\)-approximation algorithm for maximum independent set of connected subgraphs in a planar graph
- A PTAS for packing hypercubes into a knapsack
- A quasi-PTAS for the two-dimensional geometric knapsack problem
- A tight \((3/2+\varepsilon)\)-approximation for skewed strip packing
- Algorithms – ESA 2005
- Any-order online interval selection
- Approximating Geometric Knapsack via L-packings
- Approximating maximum independent set for rectangles in the plane
- Approximation and online algorithms for multidimensional bin packing: a survey
- Best fit bin packing with random order revisited
- Bin packing under random-order: breaking the barrier of 3/2
- Breaking the barrier of 2 for the storage allocation problem
- Computing the independence number of intersection graphs
- Dynamic approximate maximum independent set of intervals, hypercubes and hyperrectangles
- Geometric approximation algorithms
- Hitting sets online and unique-MAX coloring
- scientific article; zbMATH DE number 1003261 (Why is no real title available?)
- scientific article; zbMATH DE number 1947059 (Why is no real title available?)
- scientific article; zbMATH DE number 7788506 (Why is no real title available?)
- scientific article; zbMATH DE number 7799584 (Why is no real title available?)
- Improved approximation algorithm for two-dimensional bin packing
- Improved approximation algorithms for 2-dimensional knapsack: packing into multiple l-shapes, spirals, and more
- Improved online algorithms for knapsack and GAP in the random order model
- Interval selection in the streaming model
- Machine covering in the random-order model
- Maximum independent set of rectangles
- On streaming algorithms for geometric independent set and clique
- On-line randomized call control revisited
- On-line scheduling of jobs with fixed start and end times
- Online and dynamic algorithms for geometric set cover and hitting set
- Online independent set beyond the worst-case: secretaries, prophets, and periods
- Online independent sets.
- Online interval scheduling on a single machine with finite lookahead
- Online interval scheduling with predictions
- Online interval scheduling: Randomized and multiprocessor cases
- Online matroid intersection: beating half for random arrival
- Online piercing of geometric objects
- Online selection of intervals and t-intervals
- Optimal packing and covering in the plane are NP-complete
- Polynomial-Time Approximation Schemes for Geometric Intersection Graphs
- Polynomial-time approximation schemes for packing and piercing fat objects
- Primal beats dual on online packing LPs in the random-order model
- Primal-dual analysis for online interval scheduling problems
- Random order online set cover is as easy as offline
- Random order vertex arrival contention resolution schemes for matching, with applications
- Random-Order Models
- Randomized online computation with high probability guarantees
- Randomized online interval scheduling
- Scheduling In the random-order model
- Streaming algorithms for geometric Steiner forest
- Tight approximation algorithms for geometric bin packing with skewed items
- Tight approximation algorithms for two-dimensional guillotine strip packing
This page was built for publication: Random-order online independent set of intervals and hyperrectangles
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7253118)