Instance-sensitive robustness guarantees for sequencing with unknown packing and covering constraints

DOI10.1145/2422436.2422490zbMath1361.68100OpenAlexW2101864276WikidataQ57399751 ScholiaQ57399751MaRDI QIDQ2986896

Nicole Megow, Julián Mestre

Publication date: 16 May 2017

Published in: Proceedings of the 4th conference on Innovations in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2422436.2422490

zbMATH Keywords

sequencingknapsackuniversal solutioninstance-sensitive worst-case guaranteerobustness factor

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (7)

Packing a Knapsack of Unknown Capacity ⋮ The online knapsack problem with incremental capacity ⋮ Online knapsack of unknown capacity. How to optimize energy consumption in smartphones ⋮ Robust Randomized Matchings ⋮ Submodular Maximization with Uncertain Knapsack Capacity ⋮ Fractionally subadditive maximization under an incremental knapsack constraint ⋮ General bounds for incremental maximization

Cites Work

• Teachability in computational learning
• Measuring teachability using variants of the teaching dimension
• Teaching a smarter learner.
• Occam's razor
• Pseudorandom generators for space-bounded computation
• On the power of inductive inference from good examples
• A model of interactive teaching
• Learning from different teachers
• On the limits of efficient teachability
• In search of an easy witness: Exponential time vs. probabilistic polynomial time.
• On the complexity of teaching
• On specifying Boolean functions by labelled examples
• Recent Developments in Algorithmic Teaching
• A theory of the learnable
• Teaching Randomized Learners
• Algorithmic Learning Theory
• A theory of goal-oriented communication
• Derandomizing polynomial identity tests means proving circuit lower bounds
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Instance-sensitive robustness guarantees for sequencing with unknown packing and covering constraints