nach oben

Journal of Combinatorial Optimization

Erschienen in:

21.02.2018

Subset sum problems with digraph constraints

verfasst von: Laurent Gourvès, Jérôme Monnot, Lydia Tlilane

Erschienen in: Journal of Combinatorial Optimization | Ausgabe 3/2018

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

We introduce and study optimization problems which are related to the well-known Subset Sum problem. In each new problem, a node-weighted digraph is given and one has to select a subset of vertices whose total weight does not exceed a given budget. Some additional constraints called digraph constraints and maximality need to be satisfied. The digraph constraint imposes that a node must belong to the solution if at least one of its predecessors is in the solution. An alternative of this constraint says that a node must belong to the solution if all its predecessors are in the solution. The maximality constraint ensures that no superset of a feasible solution is also feasible. The combination of these constraints provides four problems. We study their complexity and present some approximation results according to the type of input digraph, such as directed acyclic graphs and oriented trees.

Vorheriger Artikel An exact approach for the balanced k-way partitioning problem with weight constraints and its application to sports team realignment

Nächster Artikel The QAP-polytope and the graph isomorphism problem

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

The operator “\(==\)” is the boolean test of equality; it outputs True or False.

Alimonti P, Kann V (2000) Some APX-completeness results for cubic graphs. Theor Comput Sci 237(1–2):123–134MathSciNetCrossRefMATH

Arkin EM, Bender MA, Mitchell JSB, Skiena S (2003) The lazy bureaucrat scheduling problem. Inf Comput 184(1):129–146MathSciNetCrossRefMATH

Bang-Jensen J, Hell P (1993) Fast algorithms for finding hamiltonian paths and cycles in in-tournament digraphs. Discrete Appl Math 41(1):75–79MathSciNetCrossRefMATH

Becker RI, Perl Y (1995) The shifting algorithm technique for the partitioning of trees. Discrete Appl Math 62(1–3):15–34MathSciNetCrossRefMATH

Bervoets S, Merlin V, Woeginger GJ (2015) Vote trading and subset sums. Oper Res Lett 43:99–102MathSciNetCrossRef

Biggs NL, Lloyd EK, Wilson RJ (1976) Graph theory 1736–1936. Clarendon Press, OxfordMATH

Boland N, Bley A, Fricke C, Froyland G, Sotirov R (2012) Clique-based facets for the precedence constrained knapsack problem. Math Program 133(1–2):481–511MathSciNetCrossRefMATH

Borradaile G, Heeringa B, Wilfong GT (2012) The knapsack problem with neighbour constraints. J Discrete Algorithms 16:224–235MathSciNetCrossRefMATH

Chlebík M, Chlebíková J (2008) Approximation hardness of dominating set problems in bounded degree graphs. Inf Comput 206(11):1264–1275MathSciNetCrossRefMATH

Cho G, Shaw DX (1997) A depth-first dynamic programming algorithm for the tree knapsack problem. INFORMS J Comput 9(4):431–438MathSciNetCrossRefMATH

Cieliebak M, Eidenbenz S, Pagourtzis A (2003) Composing equipotent teams. In: Fundamentals of computation theory, 14th international symposium, FCT 2003, Malmö, Sweden, August 12–15, 2003, Proceedings, pp 98–108

Cieliebak M, Eidenbenz S, Pagourtzis A, Schlude K (2008) On the complexity of variations of equal sum subsets. Nord J Comput 14(3):151–172MathSciNetMATH

Eggermont C, Woeginger GJ (2013) Motion planning with pulley, rope, and baskets. Theory Comput Syst 53(4):569–582MathSciNetCrossRefMATH

Esfahbod B, Ghodsi M, Sharifi A (2003) Common-deadline lazy bureaucrat scheduling problems. In: Dehne FKHA, Sack J, Smid MHM (eds), Algorithms and data structures, 8th international workshop, WADS 2003, Ottawa, Ontario, Canada, July 30–August 1, 2003, Proceedings, vol 2748 of lecture notes in computer science, Springer, pp 59–66

Gai L, Zhang G (2008) On lazy bureaucrat scheduling with common deadlines. J Comb Optim 15(2):191–199MathSciNetCrossRefMATH

Garey M, Johnson D (1979) Computers and intractability, vol 174. Freeman, New YorkMATH

Gourvès L, Monnot J, Pagourtzis A (2014) The lazy matroid problem. In: Diaz J, Lanese I, Sangiorgi D (eds), Theoretical computer science—8th IFIP TC 1/WG 2.2 international conference, TCS 2014, Rome, Italy, September 1–3, 2014. Proceedings, vol 8705 of lecture notes in computer science, Springer, pp 66–77

Gourvès L, Monnot J, Pagourtzis AT (2013) The lazy bureaucrat problem with common arrivals and deadlines: approximation and mechanism design. In: Fundamentals of Computation Theory, Springer, pp 171–182

Hajiaghayi MT, Jain K, Lau LC, Mandoiu II, Russell A, Vazirani VV (2006) Minimum multicolored subgraph problem in multiplex PCR primer set selection and population haplotyping. In: Alexandrov VN, van Albada GD, Sloot PMA, Dongarra J (eds) Computational science—ICCS 2006, 6th international conference, Reading, UK, May 28–31, 2006, Proceedings, Part II, vol 3992 of lecture notes in computer science, Springer, pp 758–766

Halldórsson MM (1993) Approximating the minimum maximal independence number. Inf Process Lett 46(4):169–172MathSciNetCrossRefMATH

Hastad J (1996) Clique is hard to approximate within \(n^{1-\varepsilon }\). In: Proceedings 37th annual symposium on foundations of computer science, 1996, IEEE, pp 627–636

Johnson DS, Niemi KA (1983) On knapsacks, partitions, and a new dynamic programming technique for trees. Math Oper Res 8(1):1–14MathSciNetCrossRefMATH

Kellerer H, Pferschy U, Pisinger D (2004) Knapsack problems. Springer, BerlinCrossRefMATH

Kolliopoulos SG, Steiner G (2007) Partially ordered knapsack and applications to scheduling. Discrete Appl Math 155(8):889–897MathSciNetCrossRefMATH

Kothari A, Suri S, Zhou Y (2005) Interval subset sum and uniform-price auction clearing. In: Wang L (ed) Computing and Combinatorics, 11th annual international conference, COCOON 2005, Kunming, China, August 16–29, 2005, Proceedings, vol 3595 of lecture notes in computer science, Springer, pp 608–620

Manlove D (1999) On the algorithmic complexity of twelve covering and independence parameters of graphs. Discrete Appl Math 91(1–3):155–175MathSciNetCrossRefMATH

Woeginger GJ, Yu Z (1992) On the equal-subset-sum problem. Inf Process Lett 42(6):299–302MathSciNetCrossRefMATH

Titel: Subset sum problems with digraph constraints
verfasst von: Laurent Gourvès
Jérôme Monnot
Lydia Tlilane
Publikationsdatum: 21.02.2018
Verlag: Springer US
Erschienen in: Journal of Combinatorial Optimization / Ausgabe 3/2018
Print ISSN: 1382-6905
Elektronische ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-018-0262-1

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 3/2018

Lot sizing with storage losses under demand uncertainty

On the m-clique free interval subgraphs polytope: polyhedral analysis and applications

On a general framework for network representability in discrete optimization

An exact approach for the balanced k-way partitioning problem with weight constraints and its application to sports team realignment

Robust trading mechanisms over 0/1 polytopes

Planning personnel retraining: column generation heuristics