A New Lower Bound for the Set-Partitioning Problem

DOI10.1137/0217040MaRDI QIDQ3796782zbMATH OpenOpenAlexFDO

Authors John Welliaveetil John

Publication date 1988

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0217040

zbMATH Keywords

analysis of algorithmdecision treelower boundset-partitioning

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Discrete mathematics in relation to computer science (68R99)

Recommendations

• Lower bounds on probabilistic linear decision trees
• On computing majority by comparisons
• The double selection problem
• Applications of Ramsey's theorem to decision tree complexity
• scientific article; zbMATH DE number 4164887

Cited in

(8)

• Finding the n-th largest element
• A dual ascent heuristic for obtaining a lower bound of the generalized set partitioning problem with convexity constraints
• A selectable sloppy heap
• Selection problems via \(m\)-ary queries
• scientific article; zbMATH DE number 3862434 (Why is no real title available?)
• Select with groups of 3 or 4
• Selection Algorithms with Small Groups
• scientific article; zbMATH DE number 7765400 (Why is no real title available?)

This page was built for publication: A New Lower Bound for the Set-Partitioning Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3796782)