optimization - Algorithm for deciding which elements N and M with N:M relation to keep, which maximize resulting number of pairs -

-

i have bunch of elements of 2 classes n , m related 1 in many-to-many fashion. let's call them 'restaurants' , 'dishes'. want make selection of restaurants , dishes results in largest possible number of restaurant-dish pairs. however every restaurant must serve every possible dish retain, , every dish must available in every restaurant. how go finding restaurants , dishes should kick out?

one possible (far optimal) "solution" keep restaurants serving dishes (resulting in few restaurants being retained), or dishes served in restaurants (resulting in few dishes being retained). not after, want determine optimal way make such selection, resulting in fair balance of restaurants , dishes being retained.

i working in python; in case helps anyone, here simple code generates type of many-to-many data i'm dealing with:

import numpy np  # let dish identified integer between 0 , 100 dishes = np.arange(100)  restaurants = [] k in range(30):     # restaurant have multiple dishes     # amount of dishes vary per restaurant     # e.g. between 10 , 100 here     restaurants.append(         np.random.choice(dishes,             size=np.random.randint(10, 100),             replace=false)     )

first, observe restaurants-to-dishes mapping bipartite graph. next, observe solution "all restaurants serve every dish, , dishes served every restaurant" problem complete bipartite subgraph, or biclique. finally, since looking maximize number of dish-restaurant pairs (as opposed maximizing number of included dishes or number of participating restaurants) biclique trying find called edge maximum (the other maximum biclique called vertex maximum).

the problem, therefore, can formally restated follows:

find edge maximum biclique in bipartite graph.

this problem has fast algorithm described in this paper:

yun zhang, elissa j. chesler , michael a. langston

on finding bicliques in bipartite graphs: novel algorithm application integration of diverse biological data types

the paper has pseudocode on page 4.


Comments

Post a Comment

Popular posts from this blog

ios - UITEXTFIELD InputView Uipicker not working in swift -

-
hello trying pop uipickerview view programmatically when user clicks on textfield. have tried doesn't doing anything. isn't working. nothing happening when click textfield class userprofiletableviewcontroller: uitableviewcontroller,uitextfielddelegate,uipickerviewdelegate,uipickerviewdatasource { var itempicker: uipickerview! = uipickerview() @iboutlet weak var gendertxtfield: uitextfield! var gender = ["male","female"] override func viewdidload() { super.viewdidload() gendertxtfield.delegate = self itempicker!.delegate = self itempicker!.datasource = self itempicker!.backgroundcolor = uicolor.blackcolor() self.gendertxtfield.inputview = itempicker } func numberofcomponentsinpickerview(pickerview: uipickerview) -> int{ return 1 } // returns # of rows in each component.. func pickerview(pickerview: uipickerview, numberofrowsincomponent component:...
Read more

Hatching array of circles in AutoCAD using c# -

-
i beginner in autocad plugins .i have created array of circle using following code. now, have hatch circles in array .how that??how hatch circles @ once? moreover, how can return hatch method , use hatch objects.sorry language.thanks in advance. [assembly: commandclass(typeof(beamsection.class1))] namespace beamsection { public class class1 { //class1 obj = new class1(); [commandmethod("beamatsupport")] public void addlightweightpolyline() { // current document , database document acdoc = application.documentmanager.mdiactivedocument; database accurdb = acdoc.database; promptpointresult ppr = acdoc.editor.getpoint("\nselect starting point "); var ucs = acdoc.editor.currentusercoordinatesystem; point3d startingpt = ppr.value.transformby(ucs); list<double> radius = new list<double>(); radius.add(0.5); ...
Read more