Search results for "submodular"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
162	Stanislav Zivný, David A. Cohen, Peter G. Jeavons	The Expressive Power of Binary Submodular Functions.	MFCS	2009	DBLP DOI BibTeX RDF	Decomposition of submodular functions, Pseudo-Boolean optimisation, Submodular function minimisation, Min-Cut
154	Jan Vondrák	Optimal approximation for the submodular welfare problem in the value oracle model.	STOC	2008	DBLP DOI BibTeX RDF	combinatorial auctions, matroids, submodular functions
132	Uriel Feige, Vahab S. Mirrokni, Jan Vondrák	Maximizing Non-Monotone Submodular Functions.	FOCS	2007	DBLP DOI BibTeX RDF
127	Jon Lee 0001, Vahab S. Mirrokni, Viswanath Nagarajan, Maxim Sviridenko	Non-monotone submodular maximization under matroid and knapsack constraints.	STOC	2009	DBLP DOI BibTeX RDF	approximation algorithms, matroids, knapsacks, submodular functions
106	Zoya Svitkina, Lisa Fleischer	Submodular Approximation: Sampling-based Algorithms and Lower Bounds.	FOCS	2008	DBLP DOI BibTeX RDF
102	Dániel Marx	Tractable hypergraph properties for constraint satisfaction and conjunctive queries.	STOC	2010	DBLP DOI BibTeX RDF	submodular width, constraint satisfaction, conjunctive queries, fixed-parameter tractability
92	Michel X. Goemans, Nicholas J. A. Harvey, Satoru Iwata 0001, Vahab S. Mirrokni	Approximating submodular functions everywhere.	SODA	2009	DBLP DOI BibTeX RDF
92	Stanislav Zivný, Peter Jeavons 0001	Classes of Submodular Constraints Expressible by Graph Cuts.	CP	2008	DBLP DOI BibTeX RDF
92	Fabián A. Chudak, Kiyohito Nagano	Efficient solutions to relaxations of combinatorial problems with submodular penalties via the Lovász extension and non-smooth convex optimization.	SODA	2007	DBLP BibTeX RDF
92	Satoru Iwata 0001, S. Thomas McCormick, Maiko Shigeno	Fast Cycle Canceling Algorithms for Minimum Cost Submodular Flow*.	Comb.	2003	DBLP DOI BibTeX RDF	AMS Subject Classification (2000): 90C27, 90C25, 90C35, 90B10
79	Satoru Iwata 0001, James B. Orlin	A simple combinatorial algorithm for submodular function minimization.	SODA	2009	DBLP DOI BibTeX RDF
74	Satoru Iwata 0001, Satoko Moriguchi, Kazuo Murota	A capacity scaling algorithm for M-convex submodular flow.	Math. Program.	2005	DBLP DOI BibTeX RDF	Discrete convex function, Submodular flow, Algorithm, Discrete optimization
66	Ariel Kulik, Hadas Shachnai, Tami Tamir	Maximizing submodular set functions subject to multiple linear constraints.	SODA	2009	DBLP DOI BibTeX RDF
66	Jon Lee 0001, Maxim Sviridenko, Jan Vondrák	Submodular Maximization over Multiple Matroids via Generalized Exchange Properties.	APPROX-RANDOM	2009	DBLP DOI BibTeX RDF
66	Tamás Király, Lap Chi Lau, Mohit Singh	Degree Bounded Matroids and Submodular Flows.	IPCO	2008	DBLP DOI BibTeX RDF
66	Dmitrij Schlesinger	Exact Solution of Permuted Submodular MinSum Problems.	EMMCVPR	2007	DBLP DOI BibTeX RDF
66	Makoto Yokoo, Toshihiro Matsutani, Atsushi Iwasaki	False-name-proof combinatorial auction protocol: Groves Mechanism with SubModular Approximation.	AAMAS	2006	DBLP DOI BibTeX RDF	strategy-proof, combinatorial auction
53	Elchanan Mossel, Sébastien Roch	On the submodularity of influence in social networks.	STOC	2007	DBLP DOI BibTeX RDF	social networks, coupling, viral marketing, submodularity
53	Sang-il Oum, Paul D. Seymour	Certifying large branch-width.	SODA	2006	DBLP DOI BibTeX RDF
52	Petr Skoda 0001	Computability of Width of Submodular Partition Functions.	IWOCA	2009	DBLP DOI BibTeX RDF
52	Martin C. Cooper	Minimization of Locally Defined Submodular Functions by Optimal Soft Arc Consistency.	Constraints An Int. J.	2008	DBLP DOI BibTeX RDF	Valued constraint satisfaction problem, Majority operation, Optimal soft arc consistency, Linear programming, Soft constraints, Discrete optimization, Submodularity
52	Shahar Dobzinski, Michael Schapira	An improved approximation algorithm for combinatorial auctions with submodular bidders.	SODA	2006	DBLP DOI BibTeX RDF
52	Satoru Iwata 0001, Satoko Moriguchi, Kazuo Murota	A Capacity Scaling Algorithm for M-convex Submodular Flow.	IPCO	2004	DBLP DOI BibTeX RDF
52	Toshihiro Fujito, Takatoshi Yabuta	Submodular Integer Cover and Its Application to Production Planning.	WAOA	2004	DBLP DOI BibTeX RDF
52	Satoru Iwata 0001	A Faster Scaling Algorithm for Minimizing Submodular Functions.	IPCO	2002	DBLP DOI BibTeX RDF
52	Kazuo Murota	Submodular Flow Problem with a Nonseparable Cost Function.	Comb.	1999	DBLP DOI BibTeX RDF	AMS Subject Classification (1991) Classes: 90C35, 90C27, 90C10
52	Satoru Iwata 0001, S. Thomas McCormick, Maiko Shigeno	A Strongly Polynomial Cut Canceling Algorithm for the Submodular Flow Problem.	IPCO	1999	DBLP DOI BibTeX RDF
48	Kiyohito Nagano	On Convex Minimization over Base Polytopes.	IPCO	2007	DBLP DOI BibTeX RDF	convex optimization, submodular functions
48	Liang Zhao 0013, Hiroshi Nagamochi, Toshihide Ibaraki	Greedy splitting algorithms for approximating multiway partition problems.	Math. Program.	2005	DBLP DOI BibTeX RDF	k-way cut, Multiterminal cut, Multiway partition problem, Approximation algorithm, Submodular function, Hypergraph partition
47	Subhash Khot, Richard J. Lipton, Evangelos Markakis, Aranyak Mehta	Inapproximability Results for Combinatorial Auctions with Submodular Utility Functions.	Algorithmica	2008	DBLP DOI BibTeX RDF	Combinatorial auctions, Hardness of approximation, Social welfare, Submodular
47	Satoru Iwata 0001, Lisa Fleischer, Satoru Fujishige	A combinatorial strongly polynomial algorithm for minimizing submodular functions.	J. ACM	2001	DBLP DOI BibTeX RDF	Discrete optimization, submodular function, strongly polynomial algorithm
40	Adrian Vetta	Nash Equilibria in Competitive Societies, with Applications to Facility Location, Traffic Routing and Auctions.	FOCS	2002	DBLP DOI BibTeX RDF
39	Satoru Iwata 0001	Submodular function minimization.	Math. Program.	2008	DBLP DOI BibTeX RDF	Mathematics Subject Classification (2000) 90C27
39	Gruia Calinescu, Chandra Chekuri, Martin Pál, Jan Vondrák	Maximizing a Submodular Set Function Subject to a Matroid Constraint (Extended Abstract).	IPCO	2007	DBLP DOI BibTeX RDF
39	Toshinari Itoko, Satoru Iwata 0001	Computational Geometric Approach to Submodular Function Minimization for Multiclass Queueing Systems.	IPCO	2007	DBLP DOI BibTeX RDF
39	Yogeshwer Sharma, Chaitanya Swamy, David P. Williamson	Approximation algorithms for prize collecting forest problems with submodular penalty functions.	SODA	2007	DBLP BibTeX RDF
39	Kazuo Murota, Akihisa Tamura	Application of M-Convex Submodular Flow Problem to Mathematical Economics.	ISAAC	2001	DBLP DOI BibTeX RDF
39	Kenji Kashiwabara, Masataka Nakamura, Takashi Takabatake	Integral Polyhedra Associated with Certain Submodular Functions Defined on 012-Vectors.	IPCO	1999	DBLP DOI BibTeX RDF
37	Majun Shi, Zishen Yang, Wei Wang 0032	Greedy guarantees for minimum submodular cost submodular/non-submodular cover problem.	J. Comb. Optim.	2023	DBLP DOI BibTeX RDF
37	Rishabh K. Iyer, Jeff A. Bilmes	Submodular Optimization with Submodular Cover and Submodular Knapsack Constraints.	CoRR	2013	DBLP BibTeX RDF
37	Rishabh K. Iyer, Jeff A. Bilmes	Submodular Optimization with Submodular Cover and Submodular Knapsack Constraints.	NIPS	2013	DBLP BibTeX RDF
35	Tim Roughgarden, Mukund Sundararajan	Quantifying inefficiency in cost-sharing mechanisms.	J. ACM	2009	DBLP DOI BibTeX RDF	inefficiency, Mechanism design, Steiner tree, cost sharing, submodular functions
35	Stefano Benati	An Improved Branch & Bound Method for the Uncapacitated Competitive Location Problem.	Ann. Oper. Res.	2003	DBLP DOI BibTeX RDF	competitive location models, random utility theory, heuristic concentration, data-correcting method, submodular functions
35	Ulrich Faigle, Walter Kern	An Order-theoretic Framework for the Greedy Algorithm with Applications to the Core and Weber Set of Cooperative Games.	Order	2000	DBLP DOI BibTeX RDF	antimatroid, coöperative game, Monge algorithm, Weber set, greedy algorithm, core, poset, matroid, submodular
34	Jan Vondrák	Symmetry and Approximability of Submodular Maximization Problems.	FOCS	2009	DBLP DOI BibTeX RDF	submodular functions. matroids, multilinear extension, approximation algorithms
34	Satoru Iwata 0001, Kiyohito Nagano	Submodular Function Minimization under Covering Constraints.	FOCS	2009	DBLP DOI BibTeX RDF	approximation algorithm, set cover, vertex cover, submodular function
34	Harold N. Gabow	A Framework for Cost-scaling Algorithms for Submodular Flow Problems	FOCS	1993	DBLP DOI BibTeX RDF	cost-scaling algorithms, submodular flow problems, dijoin, edge-connectivity orientation, k-edge-connected orientation, minimum-cost k-edge-connected orientation, integer linear programming, vertices, vertex weights, minimum-cost network flow
27	S. Thomas McCormick, Satoru Fujishige	Strongly polynomial and fully combinatorial algorithms for bisubmodular function minimization.	Math. Program.	2010	DBLP DOI BibTeX RDF	Mathematics Subject Classification (2000) Primary: 65K05, Secondary: 90C27, 68W40
27	Shaddin Dughmi, Tim Roughgarden, Mukund Sundararajan	Revenue Submodularity.	AMMA	2009	DBLP DOI BibTeX RDF
27	Shaddin Dughmi, Tim Roughgarden, Mukund Sundararajan	Revenue submodularity.	EC	2009	DBLP DOI BibTeX RDF	market expansion, efficiency, monotonicity, trade-offs, revenue, submodularity, vcg, optimal auctions
27	Stanislav Zivný, Peter G. Jeavons	The Complexity of Valued Constraint Models.	CP	2009	DBLP DOI BibTeX RDF
27	S. Thomas McCormick, Satoru Fujishige	Strongly polynomial and fully combinatorial algorithms for bisubmodular function minimization.	SODA	2008	DBLP BibTeX RDF
27	Vahab S. Mirrokni, Michael Schapira, Jan Vondrák	Tight information-theoretic lower bounds for welfare maximization in combinatorial auctions.	EC	2008	DBLP DOI BibTeX RDF	approximation algorithms, combinatorial auctions
27	Srikumar Ramalingam, Pushmeet Kohli, Karteek Alahari, Philip H. S. Torr	Exact inference in multi-label CRFs with higher order cliques.	CVPR	2008	DBLP DOI BibTeX RDF
27	Fang Bian, David Kempe 0001, Ramesh Govindan	Utility based sensor selection.	IPSN	2006	DBLP DOI BibTeX RDF	sub-modular, super-modular, sensor networks, complexity, utility, sensor selection
27	Uriel Feige, Jan Vondrák	Approximation algorithms for allocation problems: Improving the factor of 1 - 1/e.	FOCS	2006	DBLP DOI BibTeX RDF
27	Mariko Sakashita, Kazuhisa Makino, Hiroshi Nagamochi, Satoru Fujishige	Minimum Transversals in Posi-modular Systems.	ESA	2006	DBLP DOI BibTeX RDF
27	Sachin B. Patkar, H. Narayanan	An Efficient Practical Heuristic For Good Ratio-Cut Partitioning.	VLSI Design	2003	DBLP DOI BibTeX RDF
27	David D. Yao	S-modular games, with queueing applications.	Queueing Syst. Theory Appl.	1995	DBLP DOI BibTeX RDF	submodularity/supermodularity, control of queues, convergence, Nash equilibrium, Noncooperative games
26	Erik D. Demaine, Morteza Zadimoghaddam	Scheduling to minimize power consumption using submodular functions.	SPAA	2010	DBLP DOI BibTeX RDF	pre-emptive scheduling, sleep state, approximation algorithms, multiprocessor scheduling
26	James B. Orlin	A faster strongly polynomial time algorithm for submodular function minimization.	Math. Program.	2009	DBLP DOI BibTeX RDF
26	Paul Vernaza, Ben Taskar, Daniel D. Lee	Online, self-supervised terrain classification via discriminatively trained submodular Markov random fields.	ICRA	2008	DBLP DOI BibTeX RDF
26	Deeparnab Chakrabarty, Gagan Goel	On the Approximability of Budgeted Allocations and Improved Lower Bounds for Submodular Welfare Maximization and GAP.	FOCS	2008	DBLP DOI BibTeX RDF
26	Jérôme Darbon	Global Optimization for First Order Markov Random Fields with Submodular Priors.	IWCIA	2008	DBLP DOI BibTeX RDF
26	Arash Asadpour, Hamid Nazerzadeh, Amin Saberi	Stochastic Submodular Maximization.	WINE	2008	DBLP DOI BibTeX RDF
26	Tomás Kroupa	Geometry of Cores of Submodular Coherent Upper Probabilities and Possibility Measures.	SMPS	2008	DBLP DOI BibTeX RDF	Coherent upper probability, Core, Possibility measure
26	James B. Orlin	A Faster Strongly Polynomial Time Algorithm for Submodular Function Minimization.	IPCO	2007	DBLP DOI BibTeX RDF
26	Subhash Khot, Richard J. Lipton, Evangelos Markakis, Aranyak Mehta	Inapproximability Results for Combinatorial Auctions with Submodular Utility Functions.	WINE	2005	DBLP DOI BibTeX RDF
26	Satoru Iwata 0001	A fully combinatorial algorithm for submodular function minimization.	SODA	2002	DBLP BibTeX RDF
26	Fedor V. Fomin, Dimitrios M. Thilikos	On the Monotonicity of Games Generated by Symmetric Submodular Functions.	WG	2001	DBLP DOI BibTeX RDF
26	Hiroshi Nagamochi, Toshihide Ibaraki	Polyhedral Structure of Submodular and Posi-modular Systems.	ISAAC	1998	DBLP DOI BibTeX RDF
26	David Hartvigsen	A Submodular Optimization Problem with Side Constraints.	IPCO	1996	DBLP DOI BibTeX RDF
24	Cheng Lu, Wenguo Yang, Suixiang Gao	Streaming algorithms for maximizing the difference of submodular functions and the sum of submodular and supermodular functions.	Optim. Lett.	2023	DBLP DOI BibTeX RDF
24	Niv Buchbinder, Moran Feldman	Constrained Submodular Maximization via New Bounds for DR-Submodular Functions.	CoRR	2023	DBLP DOI BibTeX RDF
24	Zongqi Wan, Jialin Zhang, Wei Chen, Xiaoming Sun 0001, Zhijie Zhang	Bandit Multi-linear DR-Submodular Maximization and Its Applications on Adversarial Submodular Bandits.	CoRR	2023	DBLP DOI BibTeX RDF
24	Cyrus Cousins, Vignesh Viswanathan, Yair Zick	The Good, the Bad and the Submodular: Fairly Allocating Mixed Manna Under Order-Neutral Submodular Preferences.	CoRR	2023	DBLP DOI BibTeX RDF
24	Madhavan R. Padmanabhan, Yanhui Zhu, Samik Basu 0001, Aduri Pavan	Maximizing submodular functions under submodular constraints.	UAI	2023	DBLP BibTeX RDF
24	Cyrus Cousins, Vignesh Viswanathan, Yair Zick	The Good, the Bad and the Submodular: Fairly Allocating Mixed Manna Under Order-Neutral Submodular Preferences.	WINE	2023	DBLP DOI BibTeX RDF
24	Zongqi Wan, Jialin Zhang, Wei Chen, Xiaoming Sun 0001, Zhijie Zhang	Bandit Multi-linear DR-Submodular Maximization and Its Applications on Adversarial Submodular Bandits.	ICML	2023	DBLP BibTeX RDF
24	Xiaofei Liu, Weidong Li 0002	Combinatorial approximation algorithms for the submodular multicut problem in trees with submodular penalties.	J. Comb. Optim.	2022	DBLP DOI BibTeX RDF
24	Xin Wang, Suogang Gao, Bo Hou, Lidong Wu, Wen Liu 0009	Approximation algorithms for the submodular edge cover problem with submodular penalties.	Theor. Comput. Sci.	2021	DBLP DOI BibTeX RDF
24	Pierre Perrault, Jennifer Healey, Zheng Wen, Michal Valko	On the Approximation Relationship between Optimizing Ratio of Submodular (RS) and Difference of Submodular (DS) Functions.	CoRR	2021	DBLP BibTeX RDF
24	Naoto Ohsaka, Tatsuya Matsuoka	Approximation algorithm for submodular maximization under submodular cover.	UAI	2021	DBLP BibTeX RDF
24	Tatsuya Matsuoka, Naoto Ohsaka	Maximization of Monotone k-Submodular Functions with Bounded Curvature and Non-k-Submodular Functions.	ACML	2021	DBLP BibTeX RDF
24	Rad Niazadeh, Tim Roughgarden, Joshua R. Wang	Optimal Algorithms for Continuous Non-monotone Submodular and DR-Submodular Maximization.	J. Mach. Learn. Res.	2020	DBLP BibTeX RDF
24	Akbar Rafiey, Yuichi Yoshida	Fast and Private Submodular and k-Submodular Functions Maximization with Matroid Constraints.	CoRR	2020	DBLP BibTeX RDF
24	Lintao Ye, Shreyas Sundaram	Distributed Maximization of Submodular and Approximately Submodular Functions.	CoRR	2020	DBLP BibTeX RDF
24	Lintao Ye, Shreyas Sundaram	Distributed Maximization of Submodular and Approximately Submodular Functions.	CDC	2020	DBLP DOI BibTeX RDF
24	Akbar Rafiey, Yuichi Yoshida	Fast and Private Submodular and k-Submodular Functions Maximization with Matroid Constraints.	ICML	2020	DBLP BibTeX RDF
24	Chao Qian 0001, Yang Yu 0001, Ke Tang 0001, Xin Yao 0001, Zhi-Hua Zhou	Maximizing submodular or monotone approximately submodular functions by multi-objective evolutionary algorithms.	Artif. Intell.	2019	DBLP DOI BibTeX RDF
24	Victoria G. Crawford, Alan Kuhnle, My T. Thai	Submodular Cost Submodular Cover with an Approximate Oracle.	CoRR	2019	DBLP BibTeX RDF
24	Victoria G. Crawford, Alan Kuhnle, My T. Thai	Submodular Cost Submodular Cover with an Approximate Oracle.	ICML	2019	DBLP BibTeX RDF
24	Rad Niazadeh, Tim Roughgarden, Joshua R. Wang	Optimal Algorithms for Continuous Non-monotone Submodular and DR-Submodular Maximization.	CoRR	2018	DBLP BibTeX RDF
24	Wenruo Bai, William Stafford Noble, Jeff A. Bilmes	Submodular Maximization via Gradient Ascent: The Case of Deep Submodular Functions.	NeurIPS	2018	DBLP BibTeX RDF
24	Rad Niazadeh, Tim Roughgarden, Joshua R. Wang	Optimal Algorithms for Continuous Non-monotone Submodular and DR-Submodular Maximization.	NeurIPS	2018	DBLP BibTeX RDF
24	Naoyuki Kamiyama	A note on the submodular vertex cover problem with submodular penalties.	Theor. Comput. Sci.	2017	DBLP DOI BibTeX RDF
24	Naoyuki Kamiyama	Submodular Function Minimization with Submodular Set Covering Constraints and Precedence Constraints.	WAOA	2017	DBLP DOI BibTeX RDF
24	Dachuan Xu, Fengmin Wang, Donglei Du, Chenchen Wu	Approximation algorithms for submodular vertex cover problems with linear/submodular penalties using primal-dual technique.	Theor. Comput. Sci.	2016	DBLP DOI BibTeX RDF
24	Sin-Shuen Cheung	The Submodular Facility Location Problem and the Submodular Joint Replenishment Problem.	WAOA	2014	DBLP DOI BibTeX RDF
24	Dachuan Xu, Fengmin Wang, Donglei Du, Chenchen Wu	Primal-Dual Approximation Algorithms for Submodular Vertex Cover Problems with Linear/Submodular Penalties.	COCOON	2014	DBLP DOI BibTeX RDF