Comparisons between linear functions can help

DOI10.1016/0304-3975(82)90041-XMaRDI QIDQ1170029zbMATH OpenFDO

Authors Marc Snir

Publication date 1982

Published in Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

linear formslinear decision treesworst case behavior of decision algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cites work

• scientific article; zbMATH DE number 3128734 (Why is no real title available?)
• scientific article; zbMATH DE number 3738914 (Why is no real title available?)
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 3261280 (Why is no real title available?)
• A lower bound of \({1\over 2}n^2\) on linear search programs for the knapsack problem
• A nonlinear lower bound on linear search tree programs for solving knapsack-problems
• Comparisons between linear functions can help
• On Finding the Maxima of a Set of Vectors
• On the Polyhedral Decision Problem
• On the (n n) lower bound for convex hull and maximal vector determination
• On the complexity of computations under varying sets of primitives
• On the complexity of computing the measure of ∪[a _i ,b _i ]
• Proving simultaneous positivity of linear forms

Cited in

(4)

• Decision trees: Old and new results.
• Comparisons between linear functions can help
• Lower bounds for sorting of sums
• Selection problems via \(m\)-ary queries

This page was built for publication: Comparisons between linear functions can help

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