arbitrarycolourfulip12

MATHEMATICSOFOPERATIONSRESEARCHVol.
22,No.
3,August1997PrintedinU.
S.
A.
COLOURFULLINEARPROGRAMMINGANDITSRELATIVESIMREBARANYANDSHMUELONNWeconsiderthefollowingColourfulgeneralizationofLinearProgramming:givensetsofpointsS,.
.
.
,SkCRd,referredtoascolours,andapointbERd,decidewhetherthereisacolourfulT={s.
.
.
,SksuchthatbEconv(T),andifthereisone,findit.
LinearProgrammingisobtainedbytakingk=d+1andS==Sd,+.
+Ifk=d+1andbEnfI+conv(S)thenasolutionalwaysexists:wedescribeanefficientiterativeapproximationalgorithmforthisproblem,thatfindsacolourfulTwhoseconvexhullcontainsapointe-closetob,andanalyzeitsrealarithmeticandTuringtimecomplexities.
Incontrast,weshowthatColourfulLinearProgrammingisstronglyAT-complete.
WeconsideraclassoflinearalgebraicrelativesofColourfulLinearProgramming,andgiveacomputationalcomplexityclassificationoftherelateddecisionandcountingproblemsthatarise.
Wealsointroduceanddiscussthecomplexityofahierarchyof(w,,w2)-Matroid-Basis-Nonbasisproblems,andgiveanapplicationofColourfulLinearProgrammingtothealgorithmicproblemsofTverberg'stheoremincombinatorialgeometry.
1.
Introduction.
Theso-calledCaratheodory'stheoremsaysthefollowing:ifasetSCRdofpointsind-spacecontainsapointbinitsconvexhull,thenbEconv(T)forsomesubsetTcScontainingatmostd+1points.
Thisstatementallowstoposetheproblemoflinearprogramminginthefollowingway.
Linearprogrammingproblem.
GivenafinitesetSCQdandapointbEUd,decidewhetherthereisasubsetTcSofsizeatmostd+1suchthatbEconv(T),andifthereisone,findit.
Caratheodory'stheoremadmitsacolourfulgeneralization,duetoBatrany(1982).
Tostateit,weusethefollowingterminology:givenafamilyofsetsSI,SkCRd,referredtoascolours,acolourfulsetisasetT={s,.
.
.
,Sk}wheresiESiforalli.
THEOREM1.
1.
COLOURFULCARATHIODORY'STHEOREM.
Ifeachofd+1givencoloursSo,.
.
.
,SdCRdind-spacecontainsthepointbinitsconvexhull,thenbEconv(T)forsomecolourfulsetT={S,.
.
.
,s}.
AproofofTheorem1.
1willbegiveninthenextsection.
ThespecializationofthistheoremtoCaratheodory'sisobtainedwhenS=So=.
=Sd.
ThefollowingalgorithmicproblemsuggestedbyTheorem1.
1isanaturalgeneralizationoftheLinearProgrammingProblem.
Colourfullinearprogrammingproblem.
GivencoloursS1,.
.
.
,SkCQdandapointbEQd,decidewhetherthereisacolourfulT={sl,.
.
.
,sksuchthatbEconv(T),andifthereisone,findit.
ThespecializationofthisproblemtolinearprogrammingisobtainedbytakingS=SI-=.
=Sd+1Inthisarticlewestudythecomputationalcomplexityofthisproblemanditsrelativesinlinearalgebra,matroidtheory,andcombinatorialgeometry.
Ourmotivationistwofold.
ReceivedSeptember5,1995;revisedJune4,1996,September6,1996,andOctober14,1996.
AMS1991subjectclassification.
Primary:90C05;secondary:90C10,90C60,68Q25.
OR/MSsubjectclassification.
Primary:Programming/Linear;Secondary:Programming/Integer,Analysisofalgorithms/Computationalcomplexity.
Keywords.
Linearprogramming,integerprogramming,computationalcomplexity,combinatorialgeometry,matroid,enumeration,permanent,polytope,Caratheodory'stheorem,Tverberg'stheorem,transversal,partition,#P,NP.
5500364-765X/97/2203/0550/$05.
00CopyrightC1997,InstituteforOperationsResearchandtheManagementSciencesCOLOURFULLINEARPROGRAMMINGANDITSRELATIVESFirst,thedeterminationofthecomplexityoftheproblem(particularlyinthecasecoveredbyTheorem1.
1)isaveryimportanttheoreticalissue:ourTheorems4.
4and6.
1describedbelowprovideastepinthatdirectionbygivingcontrastingpositiveandnegativeresultsonthecomplexityoftheproblem.
Second,colourfullinearprogramminghasvariousapplications.
Wediscussonesuchapplicationtocombinatorialgeometryin7andbrieflymentionanotherin8.
Abroaderaccountofotherapplicationsandconsequencesofcolourfullinearprogrammingwillappearelsewhere.
RelatedcolourfulconjecturesanddeterminantalidentitiescanbefoundinarecentarticlebyOnn(1997).
Anoverviewofthepaperisasfollows.
In2and3weprovidearatherefficientapproximationalgorithmforcolourfullinearprogrammingandanalyzeitsrealarithmeticcomplexity.
In4weanalyzetheTuringtimecomplexityforrationaldata.
Wealsoshowhowtousetheapproximationalgorithmtosolvecolourfullinearprogrammingexactly.
In5wegiveacomputationalcomplexityclassificationofahierarchyofrelateddecisionandcountingproblemsinlinearalgebra.
Wealsointroduceanddiscussthecomplexityofahierarchyof(wl,w2)-Matroid-Basis-Nonbasisproblems.
In6weshowthatcolourfullinearprogrammingisstronglyXP-complete.
In7wegiveanapplicationofcolourfullinearprogrammingtothealgorithmicproblemofTverberg'stheoremincombinatorialgeometry.
Weconcludewithabriefdiscussion.
Hereisamoredetaileddescriptionofthecontentsofthearticleandthemainresults.
In2-4westudyanapproximationalgorithmforcolourfullinearprogramming.
Weconcentrateonthecasek=d+1andb=0Enfli+conv(Si)whereasolutionisguaranteedtoexist,butneedstobefound.
Givenane>0,thealgorithmfindsacolourfulTwhichise-closeto0,thatis,whoseconvexhullcontainsapointwhichise-closeto0.
Interestingly,ouralgorithmspecializes,inthecaseSI=.
.
.
=Sd+l,toanalgorithmofvonNeumannforlinearprogramming.
AssumingthateachSicontainsatmostnpoints,thatthepointsarenormalized,andthataballB(0,p)iscontainedinnf/+lconv(Si),weobtainthefollowingresultsontherealarithmeticcomplexityand,forrationaldata,ontherunningtimeonaTuringmachine,respectively(see3-4fortheprecisestate-ments):*Theorem3.
1.
Thenumberofrealarithmeticoperationstakenbythealgorithmtofindacolourfulsetcontainingapointe-closeto0isO(((nd+d4)lp2)log(l/e)).
*Theorem4.
3.
Forrationaldata,thealgorithmfindsacolourfulsetcontainingapointe-closeto0intimewhichispolynomialinthebitsizeLoftheinputpointsandinlog(1/e)and1/p.
Wealsoshowthatbysuitablychoosingeitispossibletoconverttheapproximationalgorithmtoanalgorithmforanexactsolutionofcolourfullinearprogrammingonrationaldata.
Wearegratefultoarefereeforhisquestionwhichpromptedustoderivethefol-lowingresult.
*Theorem4.
4.
FornormalizedrationaldatathereisanalgorithmthatfindsacolourfulsetTcontaining0initsconvexhullintimepolynomialinthebitsizeLoftheinputpointsandin1/p.
In5and6wegiveacomputationalcomplexityclassificationofahierarchyofrelatedproblems.
ColourfullinearprogrammingisequivalenttodecidingifSi,.
.
.
.
,SkadmitacolourfulTwhichispositivelydependent.
Replacing"positively"by"linearly"and"dependent"by"independent,"wegetfourdecisionandrelatedcountingproblems.
Wehavethefollowingresults,thehardnessonesholdingevenifthenumberkofsetsequalsthedimensiond.
*Theorem5.
4.
Allfourcountingproblemsare#P-complete.
*Theorems5.
1and5.
3.
Thecomplexityofdecidingtheexistenceofacolourfulsetofeachofthetypesaboveisgivenbythefollowingtable:551I.
BARANYANDS.
ONNLinearlyPositivelyDependentNP-completeNP-completeIndependentPolynomialTime*Theorem6.
1.
ColourfullinearprogrammingisstronglySP-complete.
WealsodiscussthecomplexityofthefollowinghierarchyofBasis-Nonbasismatroidproblems,oneforeachpair(wl,w2)ofpositivenumbers:itistheproblemofdeciding,givenwl+w2matroids,whetherthereisasubsetwhichisabasisinthefirstw,matroidsbutnotintheothers.
Countingproblemsrelatedtothishierarchywillbestudiedelsewhere,inanextensionofKleinschmidtandOnn(1996).
In7weturntoanapplicationtoaproblemfromcombinatorialgeometrymotivatedbyTverberg'stheorem:givenasetofpointsSCQdandapositiveintegerk,acolouring(partition)S=W=ISisuchthatn=lconv(Si)#0issought.
BasedonarecentresultbySarkaria(1992),thefollowingstatementisderived(see7fortheprecisestatement).
*Theorem7.
2.
Thedecision,counting,andsearchTverbergcolouringproblemsarepolynomialtimereducibletocorrespondingsuitableproblemsofcolourfullinearpro-gramming.
Weconcludewithabriefdiscussionofanotherapplicationtocomputationalgeometry.
OurTheorem4.
4,whichguaranteesanefficientalgorithmforcolourfullinearprogram-mingwhenk=d+1andtheconvexhullofeachcolourcontainsaballofpositivevolume,standsincontrastwithourTheorem6.
1whichassertsthatcolourfullinearpro-grammingisstronglyP-complete.
Thismakesussuggestthefollowingquestion,whichinthefollowingformremainsopen,asanoutstandingproblemontheborderlinebetweentractableandintractablecomputationalproblems.
QUESTION1.
2.
GivencoloursSo,.
.
.
,SdCQdsuchthat0En=oconv(Si),isitpossibletofindacolourfulT={So,.
.
.
,sd}suchthat0Econv(T),whichisguaranteedtoexist,inpolynomialtime2.
Approximatingacolourfulpoint.
Asweshallseeinfollowingsections,colourfullinearprogrammingiscomputationallyhard.
Thereforewefirststudytheproblemofapproximatingthecolourfulpoint.
Thiswillalsoleadtoanexactsolutionin4.
So,weconsidertheproblemofsearchingforacolourfulsetTsuchthatconv(T)containsapointwhichise-closeto0.
Inthissectionandthenexttwowedescribeandanalyzeacertainiterativepivotingalgorithmforsuchanapproximation.
Interestingly,whenSo=.
=Sd,ouralgorithmsessentiallyspecializestoanalgorithmofvonNeumannforlinearprogramming(seeDantzig1992).
Soouralgorithmcanberegardedasa"colourful"refinementofvonNeumann'salgorithm.
Ifanyoftheinputpointsistheoriginthenanycolourfulsetcontainingitisasolution.
So,withoutlossofgeneralityweassumethatnoinputpointis0andthattheinputisnormalized,thatis,thenormofeachpointsEU=oSisatisfies1sIss|2.
Thereasonwedonotsimplyassumesl=1isthatwewanttodealwithrationaldataaswell.
Notethatnormalizinganarbitraryinputiseasytodo:withrealarithmeticcomputationsimplydividesbyitsnormIs;withaTuringmachineonrationaldata,firstscalesEQdtohaveintegercomponents,andthendivideitbythelargestintegernsatisfyingn2Is2.
WeshallextendtheanalysistothesituationwhereweknowthataEuclideanballB(0,p)ofradiuspabout0iscontainedintheconvexhullofeachmonochromaticsetSi.
For552COLOURFULLINEARPROGRAMMINGANDITSRELATIVESpositiveptheconvergenceturnsouttobemuchfaster.
So,weaddressthefollowingproblem.
Colourfulpointapproximationproblem.
Givene>0,p>0,andnormalizedsetsSo,.
.
.
.
.
SdofpointsinRd,eachsatisfyingB(0,p)Cconv(Si),findacolourfulsetwhoseconvexhullcontainsapointxsatisfyingIxIE.
Inthissectionwedescribeaniterativealgorithmforthisproblemandboundthenumberofiterationsrequired.
Eachiterationinvolvesaminimumnormcomputationoverapoly-tope,whichisafairlyheavytask.
Inthenextsectionwedescribeavariantofthealgorithmwhichavoidsminimumnormcomputations,discussthedetailsofitsefficientimplemen-tation,andanalyzeitsrealarithmeticcomplexity.
In4weanalyzethecomputationalcomplexityonaTuringmachineforrationaldata.
ThefollowingalgorithmmaintainsineachintermediateiterationacolourfulsetTk=to,.
.
.
,td}andapproximatingpointxkEconv(Tk).
Algorithm1.
*Initialization.
Putk=1.
PickanarbitrarycolourfulsetT,={to,.
.
.
,td}.
Letxlbethepointofminimumnorminconv(T1).
*Iteration.
IfIxkI-ethenstopandoutputTkandXk.
Otherwiseupdatethecolourfulsetasfollows:chooseacolourisuchthatxkEconv(Tk\{ti);chooseapointtESiminimizingtheinnerproduct(Xk,t);updateti:=tandletTk+l={to,td}betheresultingnewcolourfulset.
Letxk+lbethepointofminimumnorminconv(Tk+).
Incrementkandproceedtothenextiteration.
Notethatinthekthiterationeitherxk=0andthealgorithmstops,oritispossibletochooseacolouritobeexchanged:eitherconv(Tk)isfulldimensionalandxkliesonitsboundary,orconv(Tk)hasaffinedimensionlessthand;inbothcasesxkcanbeexpressedasaconvexcombinationofatmostdpointsfromTkbytheusualCaratheodorytheorem.
Wenowderiveanupperboundonthenumberofiterations(Lemma2.
2below),whichturnsouttobenoworsethanforvonNeumann'snoncolourfulalgorithm(Dantzig1992,Freund1995).
PROPOSITION2.
1.
Lete>0and0-p-1,andletSo,.
.
.
,SdCIRdbenormalizedsetsofpoints,eachsatisfyingB(0,p)Cconv(Si).
Then,whenAlgorithm1isapplied,thefollowingrecursionsholdwhileXk+0:(11-(1Xk\2(1)Ifp=0:>-+'P>O:Ix,l2Ip12-t12iXkl24[Xk2'andforp>0:(ItI2-p2t)IX2_/Xp22It1t21-4xkiNow(Xk,ti)-0andO--p-1,andletSo,.
.
,SdCRdbenormalizedsetsofpoints,eachsatisfyingB(O,p)Cconv(Si).
ThenwehavethefollowingupperboundsonthenumberofiterationsperformedbyAlgorithm1tofindacolourfulpointwhichiswithindistanceefromtheorigin:(2)Ifp=O:=;IfP>O:1+-log=log.
PROOF.
Forp=0,letI=r4/e2l.
Summationoftheexpressionsin(1)fork=1,.
.
.
,-1gives>144__IX,I2-4(1X24rE2E2whichprovestheclaiminthiscase.
Forp>0,lett=4/(4-p2)>1andletI=1+[(2/logt)log(2/e)1.
Then(I-l)logt2log(2/e),sot2'andsobyProposition2.
1,Ix,I_.
lX1e22.
Sincep24-p24-224-p28so2/logt0letp:=ap.
Expresspasaconvexcombinationp=E=oXjtjofTk+1.
(5)Putk+1:=XandXk+l:=p.
Incrementkandproceedtothenextiteration.
555I.
BARANYANDS.
ONNThefollowingtheoremestablishesthecorrectnessandtherealarithmeticcomplexityofthisalgorithm.
Theproofincludesadescriptionoftheimplementationdetails.
Theanalysisisforthecaseofpositivep,butcaneasilybeadoptedtothecasep=0aswell.
Thetheoremgivesaboundonthenumberofarithmeticoperationsperformedonnor-malizeddata,whichdependspolynomiallyonthedimension,thenumberofpoints,andlog(l/e).
THEOREM3.
1.
Givenp>0,e>0,andnormalizedsetsSo.
.
.
,SdCRd,eachsatisfyingISiI-nandB(O,p)Cconv(Si),thenumberofrealarithmeticoperationstakenbyAlgorithm2tofindacolourfulsetcontainingapointc-closeto0is(nd+d41g)PROOF.
FirstweshowthatthealgorithmiscorrectandmaintainstheboundonthenumberofiterationsofLemma2.
2.
Considerthekthiterationloop.
InStep1,sinceatleastonehk=0,itispossibletoconstructthenewcolourfulsetTk+.
Next,considerStep2:thepointpandthevectorXcanbecomputedasfollows.
Let(Xk-tiXk)(ti-Xk,ti)=ti-Xk-X2Then,since(Xk,ti)S0,thepointd(ti-Xk,ti)Xk+(Xk-ti,Xk)tip=IXjtj=j=oIti-X2istheprojectionof0ontothesegment[Xk,ti],expressedasaconvexcombinationofTk+l(seeproofofProposition2.
1).
Ifnowp=0,orhj=0forsomej,thenXk+canbetakentobepanditispossibletoproceedtothenextiteration.
Otherwise,inStep3,usingGaussianeliminationitispossibletocheckifTk+isaffinelydependent,andifitis,findanontrivialaffinerelation2=o-tj=0with2d=oj=0.
Itisthenpossibletochooseasuitablemultiplier6sothatX:=X+6biremainsnonnegativeandsomeXibecomeszero,andthenproceedtothenextiteration.
IfStep4isreached,thenconv(Tk+l)isafulldimensionalsimplexcontainingp*0initsinterior.
Todeterminethepointapwherethelinelin(p)directedfrom0topentersconv(Tk+,),proceedasfollows.
Forj=0,.
.
.
,d,thislineintersectsthehyperplaneaff(Tk+I\tj})ifandonlyifthedeterminant-011.
.
11A=det_Pto'''tj_itj+i'''tdisnonzero,inwhichcasetheintersectionpointisajpwhere1aj=det[to**tj-tj+ltd].
Foreachj,ifA*0thencomputeajbytheexpressionabove,whereasifA=0thensetaj=oo.
Leta=max{aj:0--jd,aj0,thenapisin[0,p]hencecloserto0thanp,andpwillbemodifiedtop556COLOURFULLINEARPROGRAMMINGANDITSRELATIVES:=ap.
Sinceconv(Tk+1)isasimplexinthissituation,theuniquevectorXwhichexpressespasaconvexcombinationofTk+,isgivenby-1**1---1-A=to'*td__p_Ifp=0thenthealgorithmwillterminateinthefollowingiteration,whereasifp*0thenpisaboundarypointofconv(Tk+l)sosomeXiiszeroanditispossibletoproceedtothenextiteration.
Thenumberofarithmeticoperationsineachiterationcanbeboundedasfollows.
InStep1,theinnerproduct(Xk,t)iscomputedandcomparedforISi|-npointst,whichinvolvesO(nd)operations.
Step2involvesO(d2)arithmeticoperations.
TheworkinStep3isdominatedbytheGaussianelimination,whichtakesO(d3)operations.
Step4involves0(d)determinantcomputationsandonematrixinversion,eachdoneagainbyGaussianelimination.
SothisstepinvolvesO(d4)operations.
Thus,thetotalnumberofarithmeticoperationsperiterationisO(nd+d4).
ByLemma2.
2,forpositivepthenumberofiterationsisO((1/p2)log(l/e)),whichgivestheboundstatedinthetheorem.
O4.
Computationalcomplexityforrationaldata.
InthissectionwediscussthetimecomplexityonaTuringmachinewhentheinputconsistsofrationalpoints,andthepos-sibleconversionoftheapproximationalgorithmtoonethatfindsagenuinecolourfulsetcontaining0initsconvexhull.
ThebitsizeLoftheinputpointsU=oSiCQdisthetotalnumberofbinarybitsneededtoencodeallcoordinatevaluesofallthepoints.
NotethatL2d*d=oISi>d2.
Westartwiththefollowingtwopropositions.
PROPOSITION4.
1.
LetV={Vi,.
.
.
,vm}beasetofpointsinQd-ofbitsizeL.
IfOXconv(V)thenthenormofanyxEconv(V)islargerthan2-3dL.
PROOF.
Suppose0Qconv(V)andletx*bethepointofminimumnorminconv(V).
ByCaratheodory'stheoremthereisasubsetU={u,.
.
.
,uk}CVofaffinelyindepen-dentpointssuchthatx*isintherelativeinteriorofconv(U).
Thus,x*equalstheor-thogonalprojectionof0ontoaff(U).
Toexpressitlet1bethevectorofall1inQkandletAbethefullcolumnrankmatrix1*-*1U1.
.
Uk.
Weclaimthatx*=pwherepisdefinedbyPo1p=.
TAA(ATA)-'1.
P_lT(ATA)-l`Indeed,po=1,sopisanaffinecombinationoftheuihenceliesinaff(U),andPo_1p1T(AA)-1whichshowsthatthevalueof(ui,p)isthesameforalli,sop-0isorthogonaltoaff(U).
Now,thebitsizeofA(whichisthetotalnumberofbitsneededtoencodeallofitsentries)isatmostL,sothecommondenominatoroftheentriesofAisapositiveinteger557I.
BARANYANDS.
ONNqsatisfyingq-2L,andqAisanintegermatrixwhoseentriesareofabsolutevalueatmost2L.
LetBbetheadjointmatrixofq2(ATA).
TheentriesofBareproperminorsofq2(ATA),sobyHadamard'sinequalitytheyareintegersofabsolutevalueatmostd(3/2)d22dL,andso1TBld(3/2)d+222dL.
Now(ATA)-'isascalarmultipleofB,andsox*qlBl(qA)B1.
Thereforeeachcoordinateofx*isoftheformplDforsomeintegerp,withD=q'(1TB)-d(3/2)d+2.
2(2d+1)L*I->2-3dL~~D~~~~~PROPOSTION4.
2.
LetV={V1,.
.
.
,V}beasetofpointsinQd-ofbitsizeL.
Iftheinteriorofconv(V)containstheorigin0theninfactitcontainstheballB(0,2-3dL).
PROOF.
Supposetothecontrarythat0isintheinteriorofconv(V)butthereisapointxontheboundaryofconv(V)withIx2-3dLwhichisacontradiction.
[WenowproceedtodiscussthecomplexityofAlgorithm2forrationaldata.
Weneedtomakesurethatthebitsizeofthenumbersinvolvedinthecomputationsthroughoutthealgorithmremainspolynomiallyboundedinthesizeoftheinput.
ThisisachievedbyreplacingStep5intheiterationloopofAlgorithm2bythefollowingroundingstep:Roundingstepforrationaldata:letD=r32-d26'(d+)L1.
Putxk+l:=j_Oj+ltj,wherej~+1'Ed[DXr1(j=.
.
.
,d).
r=OFDXlWenowshowthatwiththeroundingstep,therunningtimeofAlgorithm2onaTuringmachinewhenappliedtonormalizedrationalinput,ispseudopolynomialinpandpoly-nomialintherestofthedata.
THEOREM4.
3.
Givenp>0,rationale>0andrationalnormalizedsetsSo,.
.
.
,SdCQdofbitsizeL,eachsatisfyingB(0,p)Cconv(Si),thetimetakenbyAlgorithm2withtheroundingsteptofindacolourfulsetcontainingapointe-closeto0ispolynomialinL,log(l/c),andlip.
PROOF.
First,weshowthattheboundofLemma2.
2onthenumberofiterationsremainsvalid.
Considerthekthiterationofthealgorithm,andletXandp=Zd=oXjtjbeascomputedinthisiterationbeforeenteringtheroundingstep.
Nowapplytheroundingstepandobtainxk+landkk+l.
Notethattheroundedkk+lisnonnegativeandsatisfiesd=oXk+=1,soexpressesXk+lasanexactconvexcombinationofthetj.
Now,foreachitheoriginisintheinteriorofconv(Si)sobyProposition4.
2wehaveB(0,2-3(d+1)L)Cconv(Si).
Letp=max{p,2-3(d+)L}.
Then558COLOURFULLINEARPROGRAMMINGANDITSRELATIVESr32dd26(d+l)L132-d-22D=e-and1-1-so4dD-E(1-1_)SinceB(O,p)Cconv(Si)foralli,weobtainbyProposition2.
1that1ldd1xk+,lI-[DXjltj=it+-XtDjl-DrjtjD=o/=0/=0-lpl+Itl-(-)l+d2IXI+II-1-11-0DI+ItilVI()xkl+Dd2-22(l-kIxl+2-2IxklSoIXk+IisaconstantfractionofIxk.
Therecursion(1)deducedinProposition2.
1canbereplacedbytherecursionIXk+1j(1+v1-~2/u)/21XkI,andananalysissimilartothatofLemma2.
2showsthatnumberofiterationsisO((1/p2)log(l/e))=0((1/p2)Xlog(l/e)).
Next,weshowthattherunningtimeperiterationispolynomiallyboundedinthedata.
SincethenumberofarithmeticoperationsperiterationcanbeboundedasintheproofofTheorem3.
1,itisenoughtoshowthatthebitsizeofthenumbersappearingthroughouttheiterationremainspolynomiallyboundedinthesizeoftheinput.
Thekeypointisthattheroundingstepmakessurethat,attheendofthe(k-1)thiteration,thenumeratorofeachXkisapositiveintegernotexceedingD,anditsdenominatorisapositiveintegernotexceedingdD.
SincelogD=O(logd+log(l/e)+dL),thisguaranteesthatthebitsizeofthevectorhkandthepointxk=2jd_0ktjusedatthebeginningofthekthiterationareO(d2L+dlog(1/e)).
Therefore,thedatamanipulatedwithineachiteration,whichconsistsonlyoftheoriginaldataandXkandxk,hassizepolynomiallyboundedintheinputsize.
Sothegrowthinsizeofnumbersisnotaccumulatedfromoneiterationtothenext.
NowtheworkintheiterationconsistsofstandardcomputationsinSteps1and2,plus0(d)GaussianeliminationsinSteps3and4.
SinceGaussianeliminationispoly-nomialtimeimplementable(seeSchrijver1986),weconcludethattherunningtimeperiterationispolynomialinLandlog(1/).
oFinally,weshowthatifeisspecifiedtobesmallenoughthenthecolourfulsetfoundbyAlgorithm2contains0initsconvexhull,andsoprovidesanexactsolutionofthecolourfullinearprogrammingproblem.
Wearegratefultoarefereeforhisquestionwhichpromptedustoderivethefollowingresult.
THEOREM4.
4.
Thereisanalgorithmthat,givenp>0andrationalnormalizedsetsSo,.
.
.
,SdinQdofbitsizeL,eachsatisfyingB(0,p)Cconv(Si),findsintimepoly-nomialinLand1/pacolourfulsetTcontaining0initsconvexhull.
559I.
BARANYANDS.
ONNPROOF.
LetLbethebitsizeoftheinputUdoSi,anddefinee=2-'3(d+L.
ApplyAlgorithm2withtheroundingstep.
ByTheorem4.
3thealgorithmstopsintimepoly-nomialinL,log(l/E)=O(dL),andl/p,andoutputsacolourfulsetTwhoseconvexhullcontainsapointxofnormIxle.
ByProposition4.
1above,conv(T)containstheoriginaswell,andsoTisanexactsolutionofthecolourfullinearprogrammingproblem.
o5.
Colourfullinearalgebraanditscomplexity.
AsetS={s,.
.
,sn,ofvectorsinRdispositivelydependentifithasanontriviallineardependencyi=li,iS=0withall,uinonnegative.
Sincethisisequivalentto0Econv(S),Caratheodory'stheoremnowsaysthatifSCIRdispositivelydependentthenithasasubsetofsizeatmostd+1whichalsois.
Thisisinanalogywiththetrivialstatementforalinearlydependentset.
GivennowafamilyofcoloursSo,.
.
.
,SdCRd,thecolourfulCaratheodorytheoremsaysthefollowing:ifeachmemberSiofthefamilyispositivelydependent,thenthefamilyadmitsapositivelydependentcolourfulsetT={sO,.
.
.
,s}.
Again,thisisinanalogywiththetrivialstatementforlineardependence.
Wenowconsiderseveralalgorithmicproblemsthatarise,andthatturnouttobehardforthelinear-dependencycaseaswell.
Foreachproblem,weshalldistinguishaDecisionproblem,aSearchproblem,andaCountingproblem.
HereweshallrestrictattentiontotheTuringmachinecomputationmodel,andtothefieldQofrationalintegers.
However,theseproblemshaveobviousanalogsoveranyfield9andanytypeofP-dependency(i.
e.
,whenthecoefficientsinthelinearrelationarerequiredtocomefromafixedsubsetPC3)andcouldbestudiedunderothermodelsofcomputationsuchasbyBlum,Shub,andSmale(1989).
Colourfulsetproblem.
Givenarek,d,andafamilyofnonemptycoloursSi,.
.
.
,SkCQd*Decideifthefamilyhasalinearly(positively)dependent(independent)colour-fulset.
*Findsuchacolourfulsetifoneexists.
*Countthenumberofsuchcolourfulsets.
Notethatthepositive-dependenceversionisthesameasthecolourfullinearprogram-mingproblem.
Alsonotethatifk=d+1thenanycolourfulsetislinearlydependent,sothelinear-dependenceversionoftheproblembecomestrivial.
Ifk=d+1andeachSiispositivelydependent,thepositive-dependenceversionofthedecisionproblemalsobecomestrivialbyTheorem1.
1.
Sothefollowingstatementissharp.
THEOREM5.
1.
Decidinglinearly(positively)dependentcolourfulsetsisMP-com-plete,evenifk=dandeachSiisitselfpositivelydependent.
PROOF.
Weprovethestatementsforthelinearandpositiveversionssimultaneously.
ClearlybothproblemsareinthecomplexityclassM.
WereducetheMP-completeproblemofPartition(seeGareyandJohnson1979)toeach.
Givenpositiveintegersa,,.
.
.
,ad,letfori=2,.
.
.
d,ddul=alel+ei,vU=-alel+Iei,i=2i=2andui=aie-ei,vi=-aie,-ei,whereel,.
.
.
,eddenotethestandardunitvectorsinQd,andletSi={ui,vi}foralli.
ItisnoweasytoverifythatthereisalinearlydependentcolourfulsetifandonlyifthereisapositivelydependentoneifandonlyifthereisapartitionIWJof[d]=1,.
.
.
,d}suchthatS,ieai=EjEaj:first,ifIWJissuchapartitionthen,cIui+-EjJvj560COLOURFULLINEARPROGRAMMINGANDITSRELATIVES=0,so{Ui:iEIUvj:jEJ}isalinearlyandpositivelydependentcolourfulset.
Conversely,letT={sl,.
.
.
,S}beacolourfulsetadmittinganontriviallinearrelation_d=lhjsj=0.
Fori=2,.
,d,byconsideringtheithcoordinateoftheequation0=Xjsjwefindthat0=i-Xi.
ThereforeX==XdandsoE=si=0aswell.
SoTisalsopositivelydependent,andthesetsI={i:si=ui}andJ=j:sj=vjformapartitionof[d]withthedesiredproperty.
ToprovethattheproblemremainsVP-com-pleteifeachSiisitselfpositivelydependent,simplytakeSi={ui,vi,-ui,-vi}.
Now,ifsI,.
.
.
,Sd}isalinearlydependentcolourfulsetwithY4=lisi,=0then,flippingthesignofbothsiandXiifnecessary,wefindanotherlinearlydependentcolourfulsetwithsiE{ui,vi}foralli,andproceedasabovetoshowthatitisalsopositivelydependentandtoconstructasuitablepartitionof[d].
]Itwouldbeinterestingtodeterminethecomplexityofdecidingtheexistenceofapositivelydependentcolourfulsetwhenk=d+1buttheSiarenotnecessarilypositivelydependent.
Relatedisthefollowinghardnessstatement.
THEOREM5.
2.
GiventwosetsS1,S2EQd,itisM-completetodecidewhetherthereisapositivelydependentsetTofsizedwithITnSI=ITnS2.
PROOF.
Byreductionfromexactpartition(GareyandJohnson1979).
Givenpositiveintegersal,.
.
.
,ad,letuiandvibeasintheproofofTheorem5.
1,andletS,={ul,.
.
.
,d}andS2={V,.
.
.
,Vd}.
ThenitiseasytoverifythatthereisasetTasdesiredifandonlythereisapartitionIWJof[d]suchthatIl=IJIand2iElai=Ejejaj.
ENotethatbytakingd/2copiesofeachofSIandS2above,thisimpliesagainthehardnessofdecidingpositivelydependentcolourfulsets.
IncontrastwithTheorem5.
1wehavethefollowingstatementobservedtogetherwithM.
Loebl.
THEOREM5.
3.
Decidinglinearlyindependentcolourfulsetscanbedoneinpoly-nomialtime.
PROOF.
LetVbethedisjointunionoftheSi(soapointofQdappearinginseveralSiwillhaveseveralcopiesinV).
DefinetwomatroidsM,,M2onVasfollows:MlwillbethematroidoflineardependenciesonV,whileM2willbethematroidwhosebasesareallcolourfulsets.
Thenak-subsetofVisalinearlyindependentcolourfulsetifandonlyifitisindependentinbothM,andM2,andsothedecision(andsearch)problemreduceto2-matroidintersection,whichcanbedoneinpolytime.
nThisproofraisessomequestionsaboutmatroids,whichwediscusslateron.
Butbeforethat,weshowthatcountingishardforallfourvariantsoftheproblem.
THEOREM5.
4.
Countinglinearly(respectively,positively)dependent(respectively,independent)colourfulsetsis#P-complete.
PROOF.
Allproblemsareclearlyin#P.
Wenowreducethe#P-completeproblemofcomputingthepermanentofa0,1)-matrix(seeValiant1979)toeach.
LetA=(Aij)besuchamatrixofsizedxd,andfori=1,.
.
.
,ddefineSi={ej:Aij=1.
Thenperm(A):=IAlr(Tcpermutationon[d]1i=1=1{1:7rpermutation,e(l)ESI,.
.
.
,e7(d)ESd}=#{linearlyindependentcolourfulsetsofSI,.
.
.
,Sd}d=IIISI-#{linearlydependentcolourfulsetsofS5,.
.
,Sd}.
i=l561I.
BARANYANDS.
ONNThisprovesthehardnessofcountinglinearlyindependentandlinearlydependenttrans-versals.
Forthepositiveanalogs,definesetsTo,.
.
.
,TdinQd+1byf~~~~~~~d.
To={-ej},Ti={ej:Aij,=1}U{ed+},=1,.
.
.
,.
j=1Itiseasytoseethatad-tupleofvectorsvl,.
.
.
,vdformsalinearlyindependenttransversalofS,,.
.
.
,Sdifandonlyifv,.
.
.
,dtogetherwith-_=ejformsapositivelydependenttransversalofTo,T1,.
.
.
,Td,soperm(A)=#{positivelydependenttransversalsofTo,.
.
.
,Td}d=HITI-#{positivelyindependenttransversalsofTo.
.
.
,T}.
i=OThelinearvariantsofthecolourfulsetproblemformaspecialcaseofageneralhier-archyofMatroidBasis-Nonbasisproblemswhichwenowintroduce.
Givenareapairw=(w,,w2)ofnonnegativeintegersandmatroidsM1,.
.
.
,Mw,+w,ofthesamerankd,definedonthesameset.
Ad-subsetoftheelementsisaw-setifitisabasisineachofthefirstw,matroidsandisnotabasisineachofthelastw2matroids.
Notethat,forcomplexityconsiderations,onehastospecifythewayinwhichthematroidsarepre-sented-e.
g.
,byanindependentsetoracle,orbyamatrixwhenthematroidsarelinear.
Matroidbasis-nonbasisproblem.
Givenareapairw=(wl,W2)ofnonnegativeinte-gers,positiveintegersdandn,andwl+w2matroidsofrankddefinedonthesamesetofnelements.
*Decideifthereexistsaw-set.
*Findaw-setifoneexists.
*Countthenumberofw-sets.
Thedecisionandsearchproblemsarepolynomialtimesolvableforw=(1,0)bytheso-calledgreedyalgorithmandforw=(2,0)bythe2-matroidintersectionalgorithmmentionedbefore,evenifthematroidsaregivenbyoracles.
Forw=(3,0)thedecisionproblemisknowntobep-complete.
Thecomplexityforw=(0,1),whichincludesasaspecialcasetheproblemofcheckingifngivenpointsind-spaceareingeneralposition,isunknown.
Theorem5.
1showsthatforw=(1,1)thedecisionproblemisSGP-complete.
Itwouldbeinterestingtosettlethecomplexityoftheseproblemsrestrictedtospecialclassesofmatroids.
Anotherinterestingproblemrelatedtothecolourfulsetproblemconcernscommonzerosofsystemsofquadraticforms.
IdentifyQdwiththevectorsubspaceoflinearformsinthealgebraofpolynomialsQ[x,,.
.
.
,Xd]intheobviousway.
Let1beanyfieldextensionofQ(possibly-=cQ).
Aquadraticformissimple(ofrank1)ifitistheproductuvoftwolinearformsu,vEQd.
THEOREM5.
5.
Decidingifasystemofrationalquadraticformshaveacommonnon-trivialzeroover9isNP-complete,evenifthenumberofformsequalsthenumberofindeterminatesandeachformissimple.
PROOF.
ByreductionfromPartition:constructdsetsSi={ui,vi,whereui,viEQd,asintheproofofTheorem5.
1.
Now,thesystemul,v,,.
.
.
,udvdofsimplequadraticformsinQ[x,Xd]admitacommonnontrivialzeroXEfdifandonlyif562COLOURFULLINEARPROGRAMMINGANDITSRELATIVESXisintheorthogonalcomplementinQdofsomecolourfulsetoftheSi,i.
e.
,ifandonlyiftheSiadmitalinearlydependentcolourfulset.
O6.
Stronghardnessofcolourfullinearprogramming.
Hereweshowthatthecol-ourfullinearprogrammingproblemisstrongly&P-complete(seeGareyandJohnson1979).
Thus,evenapseudo-polynomialtimealgorithm(ofrunningtimepolynomialintheunaryrepresentationofthedata-seeGareyandJohnson1979fortheexactdefinition)doesnotexistunlessP=(P.
THEOREM6.
1.
GivencoloursSi,.
.
.
,SdCQdsuchthat0Enf=,conv(Si),itisstronglyP/-completetodecidewhetherthereisacolourfulT={sl,.
SdIsuchthat0Econv(T).
PROOF.
Theproofisbyreductionfrom3-satisfiability.
Letf=cl\A.
.
.
cmbeagivenBooleanfunctionin3-conjunctivenormalformonvariablesxl,.
.
.
,xn,whereeachciisaclauseoftheformci=li,+l2+li,,witheachlrE{Xr,r}beingaliteral.
Letk=d=n+m,andlet{ec,.
.
.
,ecm,ex,.
.
.
,ex}denotethestandardbasisofQd,wherethefirstmunitvectorscorrespondtoclausesandthelastntovariables,sothatatypicalpointinQdisdenotedbyv=(vc,.
.
.
,vc,v,V).
WenowconstructsetsofpointsT,.
.
.
.
TmandSI,.
.
.
,SninQd,correspondingagaintoclausesandvariables,respectively,sothatmn0Efconv(T,)nconv(Sj),i=lj=landsuchthatthereisacolourfulTwith0Econv(T)ifandonlyiffissatisfiable(hereacolourfulsetisonethatcontainsonepointfromeachTiandonefromeachSj).
Foreachj=1,.
.
.
,nweconstructbelowthreevectorsvj,v',andui,andweletSi={,vjj,uj}.
Foreachi=1,.
.
.
,mweconstructbelowfivevectorsw',w'5,w9yi,andzi,andweletTi={wi',wi'5,wi'9,y',zi}.
LetA(respectively,A)bethembynincidencematrixofclausesandvariables(re-spectively,negatedvariables),namely(1ifxjEci,_1ifxjEci,Aij=AiJ=0otherwise,0otherwise.
Nowletmnmnv=(3Ai,,-A,,)ec+ex,v'=S(-A,,,+3A,l)ec+ex,1i=j=ii=lj=landforj=2,.
.
.
,n,mmvj=E(3A,i-A,i)ec,-ex,v=E(-A,j+3Aij)ei-ej.
i=li=1Fori=1,.
.
.
,mandr=1,5,9letir=_rec-ex,,y'=15ec+50e563I.
BARANYANDS.
ONNFinallyletuj=-(v+vi)andz'=-(w'1+w'5+Wi'9+y1)sothatSjandTiarepositivelydependentforalliandj.
Now,anysatisfyingassignmentforfgivesapositivelydependentcolourfulsetasfollows.
Forj=1,.
.
.
,nletfvjifxj=1,TSifJ=0.
Sincetheassignmentissatisfying,wehaveri:=2j=,siE{1,5,9},andwelett'=wi'fori=1,.
.
m.
Itistheneasytoverifythatimlt'+lj=isj=0,sothatT{t',.
.
.
t.
,s',.
.
.
.
s}ispositivelydependent.
Fortheconverse,supposeT={t,.
.
.
,tm,s,.
.
.
,s"}isacolourfulsetand/iandXiarenonnegativenumbers,notallzero,suchthata=0wherea:=/i+i=hXjsi.
Byconsideringthevariousequationsac=0andax=0forthevariouscoordinatesofa=0,wewillbeabletoexhibitasatisfyingassignmentforf.
First,notethatsomehjmustbenonzero:ifnot,then0=aci=-iti,sowheneverti*0theremustholdt4,=0sot'=zi.
Butthen0=ax,=S1pizi,whichwouldimplyti=0foralli.
Next,notethatmoreoverA,=k2=.
.
.
kn0,ands'=ueitherforalljorfornoj:thisfollowsbytheclaimjustprovedandbyconsideringtheequationsax=0forj=2,.
.
.
,n.
WenowproceedtoshowthatsE{vj,ij}forallj.
Suppose,indirectly,thatthisisnotthecase.
Then,bythestatementabove,wehavesj=uforallj.
Writek=h==h,.
Then,foralli,0=aO=C=u+iti,=3X.
(-2)+wit,ljEcisowemusthavet'>0,soti=y'andi==6X//y,=6k/15=2X/5.
Thus,m^in20=a,=Xul+iyix,=-2)+m-X50=(20m-2)X>0,i=15whichisimpossible.
ThereforeindeedsjE{v,JI},andwecandefineavariableas-signment1ifsjvj,Xj=0ifsJ=v.
Itremainstoshowthatthisassignmentissatisfyingforf,namelythateachclausecihasatleastoneliterallj=1.
Observefirstthatforalliwehave0=ac,=SIjEciks,+pit.
NowI,sJcE{-3X,X,5X,9X}soisnonzero.
Therefore,wemusthaveti*0,andsot'*z'.
Theclaimwillbeestablishedonceweprovethatt'*yieither,whichwillimplythatti0.
i=li2O,EHJ.
i=EHi=1,vieSiviESkthen(4)hence(3)hold,so(tl,.
.
.
,t}ispositivelydependent.
Thus,theDecision,Search,andCountingvariantsoftheTverbergcolouringproblemforSreducetothecorrespondingvariantsofthecolourfullinearprogrammingproblemforTi,.
.
.
,T,.
Inparticular,sincetheTiliein(k-1)(d+1)-spaceandeachispositivelydependentbyconstruction,thecolourfulCaratheodoryTheorem1.
1impliesthatifn>(k-1)(d+1)thenTI,.
.
.
,T,haveapositivelydependentcolourfulset,henceShasaTverbergk-colouring,whichprovesTverberg'sTheorem7.
1.
o8.
Discussion.
Tverberg'sTheorem7.
1andtherelatedalgorithmicproblemsreducetotheColourfulTheorem1.
1andtocolourfullinearprogramming.
Similarreductionsarepossibleforothertheoremsandrelatedalgorithmicproblems.
Oneexampleisthatoffindingaweake-net,anotionwhichhasvariousapplicationsincomputationalgeometry:asetTCRIdiscalledaweake-netforagivensetSCRdifTintersectstheconvexhullofeverye-fractionofpointsofS.
Alon,Barany,Fiiredi,andKleitman(1992)haveshownthatforeveryfinitesetSCIRdande>0,thereexistsaweake-netTofsizeatmost(d(3)Therefore,(4)566Sj-{vi:ti=vif'),COLOURFULLINEARPROGRAMMINGANDITSRELATIVES567+1)-(d+)e-(d+)(seeChazelle,Edelsbrunner,Grigni,Guibas,Sharir,andWelzl1995forimprovedbounds).
ThistheoremwascrucialinthesolutionoftheHadwiger-De-brunner(p,q)-problembyAlonandKleitman(1992).
Itispossibletoreducethisthe-oremandthealgorithmicproblemoffindingasmalle-nettothecolourfulCaratheodorytheoremandtocolourfullinearprogramming.
Abroaderaccountofotherapplicationsofcolourfullinearprogrammingwillappearelsewhere.
RelatedcolourfulconjecturesanddeterminantalidentitiescanbefoundinarecentarticlebyOnn(1997).
Acknowledgment.
TheresearchofImreBairanywaspartiallysupportedbyHungarianNationalScienceFoundationno.
4296and016937.
TheresearchofShmuelOnnwaspartiallysupportedbytheAlexandervonHumboldtStiftung,bytheFundforthePro-motionofResearchattheTechnion,andbyTechnionVPRFundno.
191-198.
ShmuelOnnisgratefultotheAlexandervonHumboldtStiftungforitssupportandtoPeterGritzmannforitshospitalityinUniversitatTrierwherepartofthisworkwasdone.
TheauthorsthankArkadiNemirovskiforveryhelpfuldiscussionsandsuggestionsandtherefereesforstimulatingremarksandquestions.
ReferencesAlon,N.
,I.
Barainy,Z.
Firedi,D.
Kleitman(1992).
Pointselectionsandweake-netsforconvexhulls.
Combin.
Prob.
Comp.
1189-200.
,D.
Kleitman(1992).
PiercingconvexsetsandtheHadwiger-Debrunner(p,q)-problem.
Adv.
Math.
96103-112.
Barany,I.
(1982).
AgeneralizationofCaratheodory'stheorem.
Discr.
Math.
40141-152.
Blum,L.
,M.
Shub,S.
Smale(1989).
Onatheoryofcomputationandcomplexityovertherealnumbers.
Bull.
AMS211-46.
Chazelle,B.
,H.
Edelsbrunner,M.
Grigni,L.
Guibas,M.
Sharir,E.
Welzl(1995).
Weakc-netsforconvexsets.
Discr.
Comp.
Geom.
131-17.
Dantzig,G.
B.
(1992).
Ane-precisefeasiblesolutiontoalinearprogramin-2iterations,ReportSOL/92/5,SystemsOptimizationLaboratory,DepartmentofOperationsResearch,StanfordUniversity.
Freund,R.
(1995).
Personalcommunication.
Garey,M.
R.
,D.
S.
Johnson(1979).
ComputersandIntractability,W.
H.
Freeman,SanFrancisco.
Kleinschmidt,P.
,S.
Onn(1996).
Signableposetsandpartitionablesimplicialcomplexes.
Discr.
Comp.
Geom.
15443-466.
Onn,S.
(1991).
OnthegeometryandcomputationalcomplexityofRadonpartitionsintheintegerlattice.
SIAMJ.
Discr.
Math.
4436-447.
(1997).
Acolorfuldeterminantalidentity,aconjectureofRota,andLatinsquares.
Amer.
Math.
Monthly104156-159.
Sarkaria,K.
S.
(1992).
Tverberg'stheoremvianumberfields.
IsraelJ.
Math.
79317-320.
Schrijver,A.
(1986).
TheoryofLinearandIntegerProgramming,JohnWiley,NewYork.
Tverberg,H.
(1966).
AgeneralizationofRadon'stheorem.
J.
LondonMath.
Soc.
41123-128.
Valiant,L.
G.
(1979).
Thecomplexityofcomputingthepermanent.
Theor.
Comput.
Sci.
8189-201.
I.
Barany:MathematicalInstituteoftheHungarianAcademyofSciences,P.
O.
Box127,Budapest,1364Hungary;e-mail:barany@math-inst.
huS.
Onn:OperationsResearch,FacultyofIndustrialEngineeringandManagement,Technion-IsraelInstituteofTechnology,32000Haifa,Israel;onn@ie.
technion.
ac.
il