Publication

Maximizing k-Submodular Functions and Beyond

Justin Dean Ward
2016
Journal Articles

Résumé

We consider the maximization problem in the value oracle model of functions defined on k-tuples of sets that are submodular in every orthant and r-wise monotone, where k >= 2 and 1

Source officielle

https://infoscience.epfl.ch/entities/publication/4c01493b-4e75-4aa7-a175-5a330ba5364b

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Graph Chat

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

Justin Dean Ward
2016
Journal Articles

Résumé

We consider the maximization problem in the value oracle model of functions defined on k-tuples of sets that are submodular in every orthant and r-wise monotone, where k >= 2 and 1

Source officielle

https://infoscience.epfl.ch/entities/publication/4c01493b-4e75-4aa7-a175-5a330ba5364b

À propos de ce résultat

Concepts associés (32)

Fonction sous-modulaire

En optimisation combinatoire, les fonctions sous-modulaires sont des fonctions d'ensemble particulières. Soient E un ensemble et f une fonction qui à tout sous-ensemble X de E associe un réel f(X), on dit que f est sous-modulaire si l'inégalité suivante est vérifiée pour tout sous-ensemble X et Y de E Les fonctions sous-modulaire peuvent être vues comme l'analogue discret des fonctions convexes.

Algorithme de Borůvka

Lalgorithme de Borůvka, est un algorithme de recherche de l'arbre couvrant de poids minimal dans un graphe pondéré. Il est aussi appelé algorithme de Sollin'. En théorie des graphes, étant donné un graphe non orienté connexe dont les arêtes sont pondérées, un arbre couvrant de poids minimal de ce graphe est un arbre couvrant (sous-ensemble qui est un arbre et qui connecte tous les sommets ensemble) dont la somme des poids des arêtes est minimale.

Algorithme

thumb|Algorithme de découpe d'un polygone quelconque en triangles (triangulation). Un algorithme est une suite finie et non ambiguë d'instructions et d’opérations permettant de résoudre une classe de problèmes. Le domaine qui étudie les algorithmes est appelé l'algorithmique. On retrouve aujourd'hui des algorithmes dans de nombreuses applications telles que le fonctionnement des ordinateurs, la cryptographie, le routage d'informations, la planification et l'utilisation optimale des ressources, le , le traitement de textes, la bio-informatique L' algorithme peut être mis en forme de façon graphique dans un algorigramme ou organigramme de programmation.

Afficher plus

Publications associées (23)

Afficher plus

Maximizing k-Submodular Functions and Beyond

Chattez avec Graph Search

Approximation Algorithms for Allocation and Network Design

Multi-robot task allocation for safe planning against stochastic hazard dynamics

Results on Sparse Integer Programming and Geometric Independent Sets