Multiway number partitioning

Number partitioning

In computer science, multiway number partitioning is the problem of partitioning a multiset of numbers into a fixed number of subsets, such that the sums of the subsets are as similar as possible. It was first presented by Ronald Graham in 1969 in the context of the Identical-machines scheduling problem. The problem is parametrized by a positive integer k, and called k-way number partitioning. The input to the problem is a multiset S of numbers (usually integers), whose sum is k*T. The associated decision problem is to decide whether S can be partitioned into k subsets such that the sum of each subset is exactly T. There is also an optimization problem: find a partition of S into k subsets, such that the k sums are "as near as possible". The exact optimization objective can be defined in several ways: * Minimize the difference between the largest sum and the smallest sum. This objective is common in papers about multiway number partitioning, as well as papers originating from physics applications. * Minimize the largest sum. This objective is equivalent to one objective for Identical-machines scheduling. There are k identical processors, and each number in S represents the time required to complete a single-processor job. The goal is to partition the jobs among the processors such that the makespan (the finish time of the last job) is minimized. * Maximize the smallest sum. This objective corresponds to the application of fair item allocation, particularly the maximin share. It also appears in voting manipulation problems, and in sequencing of maintenance actions for modular gas turbine aircraft engines. Suppose there are some k engines, which must be kept working for as long as possible. An engine needs a certain critical part in order to operate. There is a set S of parts, each of which has a different lifetime. The goal is to assign the parts to the engines, such that the shortest engine lifetime is as large as possible. These three objective functions are equivalent when k=2, but they are all different when k≥3. All these problems are NP-hard, but there are various algorithms that solve it efficiently in many cases. Some closely-related problems are: * The partition problem - a special case of multiway number partitioning in which the number of subsets is 2. * The 3-partition problem - a different and harder problem, in which the number of subsets is not considered a fixed parameter, but is determined by the input (the number of sets is the number of integers divided by 3). * The bin packing problem - a dual problem in which the total sum in each subset is bounded, but k is flexible; the goal is to find a partition with the smallest possible k. The optimization objectives are closely related: the optimal number of d-sized bins is at most k, iff the optimal size of a largest subset in a k-partition is at most d. * The uniform-machines scheduling problem - a more general problem in which different processors may have different speeds. (Wikipedia).

Partitions (#MegaFavNumbers)

A brief introduction to partitions and combinatorics. This video is part of the #MegaFavNumbers project. More videos can be found here: https://www.youtube.com/playlist?list=PLar4u0v66vIodqt3KSZPsYyuULD5meoAo

From playlist MegaFavNumbers

Karthik Chandrasekaran: lp-Norm Multiway Cut

In lp-norm multiway cut, the input is an undirected graph with non-negative edge weights along with k terminals and the goal is to find a partition of the vertex set into k parts each containing exactly one terminal so as to minimize the lp-norm of the cut values of the parts. This is a un

From playlist Workshop: Approximation and Relaxation

IAML2.21: Binary vs. multiclass classifiers

From playlist Thinking about Data

Ex 5: Division Involving Mixed Numbers - Compare Alternative and Traditional Methods

This video explains an alternative method that can be used to divide mixed numbers. The method involving obtaining a common denominator and then dividing the numerators. The video shows the alternative method and the traditional method of multiplying by the reciprocal.

From playlist Multiplying and Dividing Mixed Numbers

Dividing Whole Numbers

This video explains how to perform division using whole numbers. http://mathispower4u.yolasite.com/

From playlist Multiplying and Dividing Whole Numbers

Vivek Madan: Simple and fast rounding algorithms for directed and node weighted multiway cut

Vivek Madan: Simple and fast rounding algorithms for directed and node-weighted multiway cut In the multiway cut problem, input is an edge/node weighted graph and a set of k terminals; the goal is to remove min-weight subset of edges/nodes such that there is no path between any two termin

From playlist HIM Lectures 2015

Partitioning Line Segments

Geometry – Partitioning a Segment – Video Lecture Topics discussed include: directed line segments, ratios, slope, finding a point that partitions a segment to a specified ratio.

From playlist Geometry

4.2.1 Partitioned Matrix-Vector Multiplication

From playlist LAFF - Week 4

Wolfram Physics Project: Working Session Tuesday, Oct. 27, 2020 [Causal Multiway Systems]

This is a Wolfram Physics Project working session on Causal Multiway Systems in the Wolfram Model. Originally livestreamed at: https://twitch.tv/stephen_wolfram Stay up-to-date on this project by visiting our website: http://wolfr.am/physics Check out the announcement post: http://wolfr.

From playlist Wolfram Physics Project Livestream Archive

TeraLasso for sparse time-varying image modeling - Hero - Workshop 2 - CEB T1 2019

Alfred Hero (Univ. of Michigan) / 15.03.2019 TeraLasso for sparse time-varying image modeling. We propose a new ultrasparse graphical model for representing time varying images, and other multiway data, based on a Kronecker sum representation of the spatio-temporal inverse covariance ma

From playlist 2019 - T1 - The Mathematics of Imaging

Wolfram Physics Project: Working Session June 9, 2020 [Experimental Math on Multiway Systems | P2]

This is a Wolfram Physics Project working session on experimental mathematics on multiway systems in the Wolfram Model. This is a continuation from this video: https://youtu.be/beRski9cCec Originally livestreamed at: https://twitch.tv/stephen_wolfram Stay up-to-date on this project by vi

From playlist Wolfram Physics Project Livestream Archive

Ex5: Division Involving Mixed Numbers - Compare Alternative and Traditional Methods

From playlist Multiplying and Dividing Fractions

Physics Tools I: WolframModel/SetReplace and Related Functions

Find more information about the summer school here: https://education.wolfram.com/summer/school Stay up-to-date on this project by visiting our website: http://wolfr.am/physics Check out the announcement post: http://wolfr.am/physics-announcement Find the tools to build a universe: https:

From playlist Wolfram Summer Programs

How the NFL uses virtual reality to train for success | Jeremy Bailenson | Big Think

How the NFL uses virtual reality to train for success New videos DAILY: https://bigth.ink Join Big Think Edge for exclusive video lessons from top thinkers and doers: https://bigth.ink/Edge ---------------------------------------------------------------------------------- What if your wor

From playlist Virtual reality | Big Think

Ex: Multiplying Fractions Using Pattern Blocks

This video explains how to use pattern blocks to determine the product of two fractions. Site: http://mathispower4u.com

From playlist Multiplication and Division of Mixed Numbers

Multiplying Fractions (1 of 4: Understanding the Language)

More resources available at www.misterwootube.com

From playlist Fractions, Decimals and Percentages

Wolfram Physics Project: Working Session Saturday, June 27, 2020 [Multiway Systems]

This is a Wolfram Physics Project working session on multiway systems in the Wolfram Model. Originally livestreamed at: https://twitch.tv/stephen_wolfram Stay up-to-date on this project by visiting our website: http://wolfr.am/physics Check out the announcement post: http://wolfr.am/phys

From playlist Wolfram Physics Project Livestream Archive

What We've Learned from NKS Chapter 5: Two Dimensions and Beyond

In this episode of "What We've Learned from NKS", Stephen Wolfram is counting down to the 20th anniversary of A New Kind of Science with [another] chapter retrospective. If you'd like to contribute to the discussion in future episodes, you can participate through this YouTube channel or th

From playlist Science and Research Livestreams

IAML19.5 Single-link, complete-link, Ward's method

From playlist Hierarchical Clustering

Wolfram Physics Project: Working Session Tuesday, Jan. 5, 2021 [More Examples of Multiway Systems]

This is a Wolfram Physics Project working session on exploring more examples of multiway systems in the Wolfram Model. Begins at 5:20 Originally livestreamed at: https://twitch.tv/stephen_wolfram Stay up-to-date on this project by visiting our website: http://wolfr.am/physics Check out t

From playlist Wolfram Physics Project Livestream Archive

Multiway number partitioning

Related pages