𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the average case analysis of some satisfiability model problems

✍ Scribed by Khaled M. Bugrara; Cynthia A. Brown

Publisher
Elsevier Science
Year
1986
Tongue
English
Weight
709 KB
Volume
40
Category
Article
ISSN
0020-0255

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Average-case complexity of shortest-path
Average-case complexity of shortest-paths problems in the vertex-potential model
✍ Colin Cooper; Alan Frieze; Kurt Mehlhorn; Volker Priebe πŸ“‚ Article πŸ“… 2000 πŸ› John Wiley and Sons 🌐 English βš– 146 KB πŸ‘ 2 views

We study the average-case complexity of shortest-paths problems in the vertexpotential model. The vertex-potential model is a family of probability distributions on complete directed graphs with arbitrary real edge lengths, but without negative cycles. We show that on a graph with n vertices and wit

Average-case analysis of the bin-packing
Average-case analysis of the bin-packing problem with general cost structures
✍ Julien Bramel; WanSoo T. Rhee; David Simchi-Levi πŸ“‚ Article πŸ“… 1997 πŸ› John Wiley and Sons 🌐 English βš– 100 KB

We consider a version of the famous bin-packing problem where the cost of a bin is a concave function of the number of items in the bin. We analyze the problem from an average-case point of view and develop techniques to determine the asymptotic optimal solution value for a variety of functions. We