Optimization algorithms and methods | Covering problems

Bin covering problem

In the bin covering problem, items of different sizes must be packed into a finite number of bins or containers, each of which must contain at least a certain given total size, in a way that maximizes the number of bins used. This problem is a dual of the bin packing problem: in bin covering, the bin sizes are bounded from below and the goal is to maximize their number; in bin packing, the bin sizes are bounded from above and the goal is to minimize their number. The problem is NP-hard, but there are various efficient approximation algorithms: * Algorithms covering at least 1/2, 2/3 or 3/4 of the optimum bin count asymptotically, running in time respectively. * An asymptotic PTAS, algorithms with bounded worst-case behavior whose expected behavior is asymptotically-optimal for some discrete distributions, and a learning algorithm with asymptotically optimal expected behavior for all discrete distributions. * An asymptotic FPTAS. (Wikipedia).

Video thumbnail

Math for Liberal Studies - Lecture 1.8.1 The Bin-Packing Problem

This is the first video for Math for Liberal Studies Section 1.8: Bin Packing and Scheduling. In this lecture, I discuss the general idea behind the bin-packing problem and talk about several examples of how this problem can occur in the real world.

From playlist Math for Liberal Studies Lectures

Video thumbnail

Math for Liberal Studies - Lecture 1.8.2 One-at-a-Time Algorithms

This is the second video for Math for Liberal Studies Section 1.8: Bin Packing and Scheduling. In this lecture, I discuss two algorithms for solving bin-packing problems: the first-fit algorithm and the best-fit algorithm. I work through an example of each algorithm and discuss advantages

From playlist Math for Liberal Studies Lectures

Video thumbnail

Math for Liberal Studies: Bin-Packing Algorithms

In this video, we use two different bin-packing algorithms to solve the same problem. For more info, visit the Math for Liberal Studies homepage: http://webspace.ship.edu/jehamb/mls/index.html

From playlist Math for Liberal Studies

Video thumbnail

OCR MEI MwA B: Bin Packing: 07 Bin Packing Complexity

https://www.buymeacoffee.com/TLMaths Navigate all of my videos at https://sites.google.com/site/tlmaths314/ Like my Facebook Page: https://www.facebook.com/TLMaths-1943955188961592/ to keep updated Follow me on Instagram here: https://www.instagram.com/tlmaths/ Many, MANY thanks to Dea

From playlist OCR MEI MwA B: Bin Packing

Video thumbnail

OCR MEI MwA B: Bin Packing: 01 Introduction to Bin Packing

https://www.buymeacoffee.com/TLMaths Navigate all of my videos at https://sites.google.com/site/tlmaths314/ Like my Facebook Page: https://www.facebook.com/TLMaths-1943955188961592/ to keep updated Follow me on Instagram here: https://www.instagram.com/tlmaths/ Many, MANY thanks to Dea

From playlist OCR MEI MwA B: Bin Packing

Video thumbnail

Math for Liberal Studies - Lecture 1.8.4 Scheduling Problems

This is the last video for Math for Liberal Studies Section 1.8: Bin Packing and Scheduling. In this lecture, I discuss different types of scheduling problems and how we can apply bin-packing ideas to those problems. Specifically, I discuss the Longest-Processing-Time (LPT) algorithm and w

From playlist Math for Liberal Studies Lectures

Video thumbnail

Math for Liberal Studies - Lecture 1.8.3 Sorted-Weight Algorithms

This is the third video for Math for Liberal Studies Section 1.8: Bin Packing and Scheduling. In this lecture, I discuss variations of the first-fit and best-fit packing algorithms. In these methods, we first sort the list of objects from largest to smallest before applying the packing alg

From playlist Math for Liberal Studies Lectures

Video thumbnail

OCR MEI MwA B: Bin Packing: 05 Full-Bin Strategy Example

https://www.buymeacoffee.com/TLMaths Navigate all of my videos at https://sites.google.com/site/tlmaths314/ Like my Facebook Page: https://www.facebook.com/TLMaths-1943955188961592/ to keep updated Follow me on Instagram here: https://www.instagram.com/tlmaths/ Many, MANY thanks to Dea

From playlist OCR MEI MwA B: Bin Packing

Video thumbnail

05b Machine Learning: Curse of Dimensionality

A lecture on the curse of dimensionality. Motivation for feature selection and dimensionality reduction. This is an undergraduate / graduate course that I teach once a year at The University of Texas at Austin. We build from fundamental spatial / subsurface, geoscience / engineering model

From playlist Machine Learning

Video thumbnail

Data Preprocessing and the Short-Time Fourier Transform | Deep Learning for Engineers, Part 3

Data in its raw form might not be ideal for training a network. There are some changes we can make to the data that are often desired or sometimes necessary in order to make training faster, simpler, or to ensure that it converges on a solution in the first place. This video covers thr

From playlist Deep Learning for Engineers

Video thumbnail

Python Tutorial: How to Set the Path and Switch Between Different Versions/Executables (Mac & Linux)

In this Python Programming Tutorial, we will be learning how to set the PATH environment variable on the Mac & Linux Operating Systems. Be one of the first 200 people to sign up with this link and get 20% off your premium subscription. https://brilliant.org/cms We will also learn how to

From playlist Python Programming Beginner Tutorials

Video thumbnail

O'Reilly Webcast: Two Big Data Analysis Tricks for Everyone

Data analysis skills are critical to staying competitive in the 21st century economy. In this webcast the author of "Head First Data Analysis," Michael Milton, provides some useful tips for common data problems that everyone faces, including: -How to enhance your career (and save the

From playlist O'Reilly Webcasts

Video thumbnail

COMBINATIONS with REPETITION - DISCRETE MATHEMATICS

We take a look at combinations with repetition, and discuss integer solution problems. Visit our website: http://bit.ly/1zBPlvm Subscribe on YouTube: http://bit.ly/1vWiRxW *--Playlists--* Discrete Mathematics 1: https://www.youtube.com/playlist?list=PLDDGPdw7e6Ag1EIznZ-m-qXu4XX3A0cIz Dis

From playlist Discrete Math 1

Video thumbnail

Live CEOing Ep 400: Spatial Statistics Design Review for Wolfram Language

In this episode of Live CEOing, Stephen Wolfram reviews the design of upcoming spatial statistics functionality for the Wolfram Language. If you'd like to contribute to the discussion in future episodes, you can participate through this YouTube channel or through the official Twitch channe

From playlist Behind the Scenes in Real-Life Software Design

Video thumbnail

Lecture 15 - Backtracking

This is Lecture 15 of the COMP300E (Programming Challenges) course taught by Professor Steven Skiena [http://www.cs.sunysb.edu/~skiena/] at Hong Kong University of Science and Technology in 2009. The lecture slides are available at: http://www.algorithm.cs.sunysb.edu/programmingchallenges

From playlist COMP300E - Programming Challenges - 2009 HKUST

Video thumbnail

IMT4306 - Mobile Research

IMT4306 Mobile Research Introduction to some of the decentralization, and peer-to-peer technologies.

From playlist Archive - Research in Mobile/Wearable Tech

Video thumbnail

Matplotlib Tutorial (Part 6): Histograms

In this video, we will be learning how to create histograms in Matplotlib. This video is sponsored by Brilliant. Go to https://brilliant.org/cms to sign up for free. Be one of the first 200 people to sign up with this link and get 20% off your premium subscription. In this Python Program

From playlist Matplotlib Tutorials

Video thumbnail

PCB Wall

What to do with all those old PCBs from stuff you've taken apart...

From playlist Projects & Installations

Video thumbnail

PSY 523 Word Recognition Part 3

Lecturer: Dr. Erin M. Buchanan Missouri State University Summer/Fall 2016 PSY 523 Psychology and Language lectures covering material from Harley's The Psychology of Language: From Data to Theory. Lecture materials and assignments available at statisticsofdoom.com. https://statisticsofdoo

From playlist PSY 523 Psychology and Language

Related pages

Approximation algorithm | Configuration linear program | Polynomial-time approximation scheme | NP-hardness | Fully polynomial-time approximation scheme | Fair item allocation | Bin packing problem