Cover Image

Approximations and Hardness of Packing Partially Ordered Items

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Doron-Arad, Ilan, Kortsarz, Guy, Naor, Joseph, Schieber, Baruch, Shachnai, Hadas
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

You (Almost) Can't Beat Brute Force for 3-Matroid Intersection
by: Doron-Arad, Ilan, et al.
Published: (2024)

An EPTAS for Cardinality Constrained Multiple Knapsack via Iterative Randomized Rounding
by: Doron-Arad, Ilan, et al.
Published: (2023)

Lower Bounds for Matroid Optimization Problems with a Linear Constraint
by: Doron-Arad, Ilan, et al.
Published: (2023)

Non-Linear Paging
by: Doron-Arad, Ilan, et al.
Published: (2024)

An Algorithm-to-Contract Framework without Demand Queries
by: Doron-Arad, Ilan, et al.
Published: (2025)

Analysis of Two-variable Recurrence Relations with Application to Parameterized Approximations
by: Kulik, Ariel, et al.
Published: (2019)

Unsplittable Flow on a Short Path
by: Doron-Arad, Ilan, et al.
Published: (2024)

Fine Grained Lower Bounds for Multidimensional Knapsack
by: Doron-Arad, Ilan, et al.
Published: (2024)

Hardness and Tight Approximations of Demand Strip Packing
by: Jansen, Klaus, et al.
Published: (2024)

The Steiner Shortest Path Tree Problem
by: Asher, Omer, et al.
Published: (2025)

On the 2D Demand Bin Packing Problem: Hardness and Approximation Algorithms
by: Albers, Susanne, et al.
Published: (2025)

Optimal Preprocessing for Answering On-Line Product Queries
by: Alon, Noga, et al.
Published: (2024)

The Telephone $k$-Multicast Problem
by: Hathcock, Daniel, et al.
Published: (2024)

Online Bin Packing with Item Size Estimates
by: Gehnen, Matthias, et al.
Published: (2025)

Chasing Submodular Objectives, and Submodular Maximization via Cutting Planes
by: Buchbinder, Niv, et al.
Published: (2025)

Online Dependent Rounding Schemes for Bipartite Matchings, with Applications
by: Joseph, et al.
Published: (2023)

Hitting Meets Packing: How Hard Can it Be?
by: Focke, Jacob, et al.
Published: (2024)

Girth Approximations in the CONGEST Model
by: Chechik, Shiri, et al.
Published: (2026)

Improved Hardness of Approximation for Geometric Bin Packing
by: Ray, Arka, et al.
Published: (2023)

An Improved Approximation Algorithm for Metric Triangle Packing
by: Zhao, Jingyang, et al.
Published: (2024)

Hardness and Approximation for Coloring Digraphs
by: Chalermsook, Parinya, et al.
Published: (2026)

Approximation Algorithms for Packing Cycles and Paths in Complete Graphs
by: Zhao, Jingyang, et al.
Published: (2023)

An Improved Approximation Algorithm for Maximum Weight 3-Path Packing
by: Zhao, Jingyang, et al.
Published: (2025)

Exponential-Time Approximation (Schemes) for Vertex-Ordering Problems
by: Bentert, Matthias, et al.
Published: (2025)

Dimension-Free Correlated Sampling for the Hypersimplex
by: Joseph, et al.
Published: (2025)

Hardness and Approximation Algorithms for Balanced Districting Problems
by: Dharangutte, Prathamesh, et al.
Published: (2025)

Hardness of Approximation for Shortest Path with Vector Costs
by: Carlson, Charlie, et al.
Published: (2025)

A Tight ($3/2 + \varepsilon$)-Approximation Algorithm for Demand Strip Packing
by: Eberle, Franziska, et al.
Published: (2024)

Approximating Energy-Constrained Drone Delivery Packing Problem for Last-Mile Logistics
by: Jana, Saswata, et al.
Published: (2026)

Approximating Directed Minimum Cut and Arborescence Packing via Directed Expander Hierarchies
by: Jiang, Yonggang, et al.
Published: (2025)

Automating the Search for Small Hard Examples to Approximation Algorithms
by: Sharma, Eklavya
Published: (2025)

Parameterized Approximation for Capacitated $d$-Hitting Set with Hard Capacities
by: Lokshtanov, Daniel, et al.
Published: (2024)

Almost Tight Approximation Hardness and Online Algorithms for Resource Scheduling
by: Das, Rathish, et al.
Published: (2025)

Labeling Methods for Partially Ordered Paths
by: Euler, Ricardo, et al.
Published: (2023)

A $(\frac32+\frac1{\mathrm{e}})$-Approximation Algorithm for Ordered TSP
by: Armbruster, Susanne, et al.
Published: (2024)

Improved Approximation Algorithms and Hardness Results for Shortest Common Superstring with Reverse Complements
by: Yamano, Ryosuke, et al.
Published: (2026)

Approximations for Fault-Tolerant Total and Partial Positive Influence Domination
by: Lamprou, Ioannis, et al.
Published: (2025)

Partially Ordered Sets Corresponding to the Partition Problem
by: Kubo, Susumu
Published: (2024)

Near Linear Time Approximation Schemes for Clustering of Partially Doubling Metrics
by: Driemel, Anne, et al.
Published: (2026)

Improved Approximation Algorithms for Three-Dimensional Bin Packing
by: Kar, Debajyoti, et al.
Published: (2025)