java - What is the optimized implementation of conflict graph for combinatorial auction? -

given m bids may share subset of n items, want find best way store conflicts among bids , check whether 2 bids conflicting (i.e., share @ least 1 item). far, have tried matrix of dimension m x m isn't optimal. problem may have thousands of bids, therefore error "java out of memory space" when use square matrix implementation. then, tried triangular matrix (because original conflict matrix symmetric) without getting rid of memory issue!

any better idea?

the best way code?

thanks.

one solution use guava's table , combine list<bid> containing bids. note: below code uses lot of guava goodness:

final list<bid> allbids = lists.newarraylist(); final table<bid, bid, void> conflicts = hashbasedtable.create(); 

when store new bid, you'll (this supposes bid has .items() method return set<item>):

for (final bid bid: allbids)     if (!sets.intersection(newbid.items(), bid.items()).isempty())         conflicts.put(newbid, bid, null); allbids.add(newbid); 

then when want detect conflict between 2 bids:

return table.contains(bid1, bid2) || table.contains(bid2, bid1); 

---

you store conflicting items replacing void values set<item>s instead , put result of sets.intersection() in it:

// table becomes table<bid, bid, set<item>> sets.setview<item> set; (final bid bid: allbids) {     set = sets.intersection(newbid.items(), bid.items())     if (!set.isempty())         conflicts.put(newbid, bid, set.immutablecopy()); } allbids.add(newbid);