Vi studerar problemet med minsta submodulära kostnadsfördelning (MSCA). I detta problem får vi en ändlig mark uppsättning V och k icke-negativa submodulära uppsättning funktioner f 1,. .., f k på V. Målet är att dela upp V i k (eventuellt tom) sätter välstuderade problem såsom den icke-metriska anläggningen plats problem, multiway-cut i grafer och hypergrafer, och enhetlig metrisk märkning och dess generaliseringar kan visas vara speciella fall av MSCA. I detta dokument överväger vi en konvex-programmering avkoppling som erhålls via Lovász-extension för submodulära funktioner. Detta gör att vi kan förstå flera tidigare avkopplingar och avrundningsförfaranden på ett enhetligt sätt och även utveckla nya formuleringar och approximationsalgoritmer för flera problem. I synnerhet ger vi en (1,5 −1/k) - approximation för hypergraph multiway partition problem. Vi ger också en min {2(1−1/k), H  på }-uppskattning för hypergraph multiway cut problem när  till är den maximala hyperedge storlek. Båda problemen generaliserar multiway cut problem i grafer och hypergraph cut problem är approximation motsvarande node-viktade multiway cut problem i grafer.
Det visas i REF att en konvex programmeringsavkoppling via Lovász-tillägget följer naturligt för MINIMI SUBMODULAR-KOST ALLOCATION, och att  på rundning baserade algoritmer ger ett enhetligt sätt att förstå och förlänga flera tidigare resultat.
Submodular Cost Allocation Problem and Applications
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}