The DOI matches its Crossref record; 8 of the 9 references it cites were found in a registry or an index.
An analysis of approximations for maximizing submodular set functions—II
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
When per-pool KV capacity is slack, the partition matroid M1 is the only binding constraint and the combinatorial (lazy) greedy deployed on the fast path returns A_g with G(A_g) ≥ 1/2 G*.
“When per-pool KV capacity is slack (the common case), M 1 is the only binding constraint and the combinatorial (lazy) greedy deployed on the fast path returns A g with G ( A g ) ≥ 1 2 G ⋆ [54]”
From Janus: Joint Prefill/Decode Disaggregation with KV-Cache-Aware Multi-Cloud Routing for Edge-Adjacent LLM Serving (2026) · cites this paper as [54]
Submodular maximization (from the classical greedy analysis of Nemhauser-Wolsey-Fisher [12]) underpins cache and content placement [20]; the matroid-constrained guarantees we invoke are due to Fisher-Nemhauser-Wolsey [54] (combinatorial greedy, 1/2), Calinescu-Chekuri-Pál-Vondrák [53] (continuous greedy, 1-1/e), and, for the matroid-plus-knapsack case, Lee-Mirrokni-Nagarajan-Sviridenko [62] (local
“Submodular maximization (from the classical greedy analysis of Nemhauser-Wolsey-Fisher [12]) underpins cache and content placement [20]; the matroid-constrained guarantees we invoke are due to Fisher-Nemhauser-Wolsey [54] (combinatorial greedy, 1 2 ), Calinescu-Chekuri-Pál-Vondrák [53] (continuous greedy, 1 -1 /e ), and, for the matroid-plus-knapsack case, Lee-Mirrokni-Nagarajan-Sviridenko [62] (”
From Janus: Joint Prefill/Decode Disaggregation with KV-Cache-Aware Multi-Cloud Routing for Edge-Adjacent LLM Serving (2026) · cites this paper as [54]
Citations
Cites
An analysis of approximations for maximizing submodular set functions—I
Nemhauser, G. L., Wolsey, L. A., & Fisher, M. L. (1978) · Mathematical Programming · doi:10.1007/bf01588971 · Cited by 4,412
Self-citationP-Complete Approximation Problems
Sahni, S. K., & Gonzalez, T. F. (1976) · Journal of the ACM · doi:10.1145/321958.321975 · Cited by 1,725
Cornuéjols, G., Fisher, M. L., & Nemhauser, G. L. (1977) · Management Science · doi:10.1287/mnsc.23.8.789 · Cited by 793
Self-citationLectures on Applied Mathematics
Bungartz, H., Hoppe, R. H. W., & Zenger, C. (2000) · Springer eBooks · doi:10.1007/978-3-642-59709-1 · Cited by 772
Submodular Functions, Matroids, and Certain Polyhedra
Edmonds, J. (2003) · Lecture notes in computer science · doi:10.1007/3-540-36478-1_2 · Cited by 543
An Analysis of the Greedy Heuristic for Independence Systems
Körte, B., & Hausmann, D. (1978) · Annals of discrete mathematics · doi:10.1016/s0167-5060(08)70322-4 · Cited by 192
Worst-Case Analysis of a Placement Algorithm Related to Storage Allocation
Chandra, A. K., & Wong, C. K. (1975) · SIAM Journal on Computing · doi:10.1137/0204021 · Cited by 126
Introduction to the Theory of Matroids
Randow, R. (1975) · Lecture notes in economics and mathematical systems · doi:10.1007/978-3-642-48292-2 · Cited by 37
Flagged first, then by citations
1 of the 9 references couldn’t be matched to a known paper.
Research works printed but not linked: 2
- J. Edmonds, “Matroid partition”, in: G.B. Dantzig and A.M. Veinott, eds., Mathematics of the decision sciences, Lectures in Applied Mathematics, 11, (Am. Math. Soc. Providence, RI, 1968) pp. 333–345.
- T.A. Jenkyns, “The efficiency of the “greedy” algorithm”, in: Proceedings of the 7th S.E. Conference on combinatorics, graph theory and computing (Utilitas Mathematica, Winnipeg, 1976) pp. 341–350.
Cited by
Sorted by citations
Entropy rate superpixel segmentation
Liu, M.-Y., Tuzel, O., Ramalingam, S., & Chellappa, R. (2011) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr.2011.5995323 · Cited by 1,059
Submodular functions and convexity
Lovász, L. (1983) · Springer eBooks · doi:10.1007/978-3-642-68874-4_10 · Cited by 968
Determinantal Point Processes for Machine Learning
Kulesza, A., & Taskar, B. (2012) · now publishers, Inc. eBooks · doi:10.1561/2200000044 · Cited by 1,077
Optimal approximation for the submodular welfare problem in the value oracle model
Vondrák, J. (2008) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1374376.1374389 · Cited by 546
The simple plant location problem: Survey and synthesis
Krarup, J., & Pruzan, P. M. (1983) · European Journal of Operational Research · doi:10.1016/0377-2217(83)90181-9 · Cited by 544
Combinatorial auctions with decreasing marginal utilities
Lehmann, B., Lehmann, D. J., & Nisan, N. (2005) · Games and Economic Behavior · doi:10.1016/j.geb.2005.02.006 · Cited by 472
Conforti, M., & Cornuéjols, G. (1984) · Discrete Applied Mathematics · doi:10.1016/0166-218x(84)90003-9 · Cited by 340
A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem
Chekuri, C., & Khanna, S. (2005) · SIAM Journal on Computing · doi:10.1137/s0097539700382820 · Cited by 332
Vetta, A. R. (2003) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2002.1181966 · Cited by 320
Singer, Y. (2010) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2010.78 · Cited by 296
A Unified Continuous Greedy Algorithm for Submodular Maximization
Feldman, M., Naor, J. S., & Schwartz, R. (2011) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2011.46 · Cited by 248
Submodularity in Data Subset Selection and Active Learning
Wei, K., Iyer, R., & Bilmes, J. (2015) · International Conference on Machine Learning · Cited by 239
Non-monotone submodular maximization under matroid and knapsack constraints
Lee, J., Mirrokni, V., Nagarajan, V., & Sviridenko, M. I. (2009) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1536414.1536459 · Cited by 234
He, T., Khamfroush, H., Wang, S., Porta, T. L., & Stein, S. (2018) · IEEE International Conference on Distributed Computing Systems (ICDCS) · doi:10.1109/icdcs.2018.00044 · Cited by 237
Submodular Function Maximization via the Multilinear Relaxation and Contention Resolution Schemes
Chekuri, C., Vondrák, J., & Zenklusen, R. (2014) · SIAM Journal on Computing · doi:10.1137/110839655 · Cited by 224
Dependent Randomized Rounding via Exchange Properties of Combinatorial Structures
Chekuri, C., Vondrák, J., & Zenklusen, R. (2010) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2010.60 · Cited by 221
Tight approximation algorithms for maximum general assignment problems
Fleischer, L., Goemans, M. X., Mirrokni, V., & Sviridenko, M. I. (2006) · Cited by 218
Krause, A., Horvitz, E., Kansal, A., & Zhao, F. (2008) · ACM/IEEE International Conference on Information Processing in Sensor Networks (IPSN) · doi:10.1109/ipsn.2008.37 · Cited by 214
Service Placement and Request Scheduling for Data-Intensive Applications in Edge Clouds
Farhadi, V., Mehmeti, F., He, T., Porta, T. L., Khamfroush, H., Wang, S., Chan, K., & Poularakis, K. (2021) · IEEE/ACM Transactions on Networking · doi:10.1109/tnet.2020.3048613 · Cited by 209
Maximizing a Submodular Set Function Subject to a Matroid Constraint (Extended Abstract)
Cälinescu, G., Chekuri, C., Pál, M., & Vondrák, J. (2007) · Springer eBooks · doi:10.1007/978-3-540-72792-7_15 · Cited by 187
Maximizing Nonmonotone Submodular Functions under Matroid or Knapsack Constraints
Lee, J., Mirrokni, V., Nagarajan, V., & Sviridenko, M. I. (2010) · SIAM Journal on Discrete Mathematics · doi:10.1137/090750020 · Cited by 180
Optimal Approximation for Submodular and Supermodular Optimization with Bounded Curvature
Sviridenko, M. I., Vondrák, J., & Ward, J. (2017) · Mathematics of Operations Research · doi:10.1287/moor.2016.0842 · Cited by 183
Online Ad Assignment with Free Disposal
Feldman, J., Korula, N., Mirrokni, V., Muthukrishnan, S., & Pál, M. (2009) · Lecture notes in computer science · doi:10.1007/978-3-642-10841-9_34 · Cited by 181
Service Placement and Request Scheduling for Data-intensive Applications in Edge Clouds
Farhadi, V., Mehmeti, F., He, T., Porta, T. L., Khamfroush, H., Wang, S., & Chan, K. (2019) · IEEE Conference on Computer Communications (INFOCOM) · doi:10.1109/infocom.2019.8737368 · Cited by 177
Matroid matching and some applications
Lovász, L. (1980) · Journal of Combinatorial Theory Series B · doi:10.1016/0095-8956(80)90066-0 · Cited by 176
Fast algorithms for maximizing submodular functions
Badanidiyuru, A., & Vondrák, J. (2013) · ACM-SIAM Symposium on Discrete Algorithms (SODA) · doi:10.1137/1.9781611973402.110 · Cited by 170
Constrained Non-monotone Submodular Maximization: Offline and Secretary Algorithms
Gupta, A., Roth, A., Schoenebeck, G. R., & Talwar, K. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-17572-5_20 · Cited by 168
Submodular Maximization over Multiple Matroids via Generalized Exchange Properties
Lee, J., Sviridenko, M. I., & Vondrák, J. (2010) · Mathematics of Operations Research · doi:10.1287/moor.1100.0463 · Cited by 166
QoE-Driven Mobile Edge Caching Placement for Adaptive Video Streaming
Li, C., Toni, L., Zou, J., Xiong, H., & Pascal Frossard, B. (2017) · IEEE Transactions on Multimedia · doi:10.1109/tmm.2017.2757761 · Cited by 152
A heuristic lagrangean algorithm for the capacitated plant location problem
Barceló, J., & Casanovas, J. (1984) · European Journal of Operational Research · doi:10.1016/0377-2217(84)90211-x · Cited by 140
Submodularity and greedy algorithms in sensor scheduling for linear dynamical systems
Jawaid, S. T., & Smith, S. L. (2015) · Automatica · doi:10.1016/j.automatica.2015.08.022 · Cited by 137
Fast Greedy Algorithms in MapReduce and Streaming
Kumar, R., Moseley, B., Vassilvitskii, S., & Vattani, A. (2015) · ACM Transactions on Parallel Computing · doi:10.1145/2809814 · Cited by 135
Submodular function maximization via the multilinear relaxation and contention resolution schemes
Chekuri, C., Vondrák, J., & Zenklusen, R. (2011) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1993636.1993740 · Cited by 133
Database Location in Computer Networks
Fisher, M. L., & Hochbaum, D. S. (1980) · Journal of the ACM · doi:10.1145/322217.322226 · Cited by 130
Self-citationAdaptive Seeding in Social Networks
Seeman, L., & Singer, Y. (2013) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2013.56 · Cited by 126
Tight information-theoretic lower bounds for welfare maximization in combinatorial auctions
Mirrokni, V., Schapira, M., & Vondrák, J. (2008) · ACM Conference on Electronic Commerce (EC) · doi:10.1145/1386790.1386805 · Cited by 125
Liu, M.-Y., Tuzel, O., Ramalingam, S., & Chellappa, R. (2013) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2013.107 · Cited by 117
How to win friends and influence people, truthfully
Singer, Y. (2012) · ACM International Conference on Web Search and Data Mining (WSDM) · doi:10.1145/2124295.2124381 · Cited by 109
Symmetry and Approximability of Submodular Maximization Problems
Vondrák, J. (2013) · SIAM Journal on Computing · doi:10.1137/110832318 · Cited by 108
Monotone Submodular Maximization over a Matroid via Non-Oblivious Local Search
Filmus, Y., & Ward, J. (2014) · SIAM Journal on Computing · doi:10.1137/130920277 · Cited by 96
Resilient Active Target Tracking With Multiple Robots
Zhou, L., Tzoumas, V., Pappas, G. J., & Tokekar, P. (2018) · IEEE Robotics and Automation Letters · doi:10.1109/lra.2018.2881296 · Cited by 95
Recent Developments in Discrete Convex Analysis
Murota, K. (2008) · Springer eBooks · doi:10.1007/978-3-540-76796-1_11 · Cited by 92
An Efficient Downlink Radio Resource Allocation with Carrier Aggregation in LTE-Advanced Networks
Liao, H.-S., Chen, P.-Y., & Chen, W.-T. (2014) · IEEE Transactions on Mobile Computing · doi:10.1109/tmc.2013.2297310 · Cited by 91
Corah, M., & Michael, N. (2018) · Autonomous Robots · doi:10.1007/s10514-018-9778-6 · Cited by 91
Submodular maximization meets streaming: matchings, matroids, and more
Chakrabarti, A., & Kale, S. (2015) · Mathematical Programming · doi:10.1007/s10107-015-0900-7 · Cited by 91
Submodular secretary problem and extensions
Bateni, M., Hajiaghayi, M., & Zadimoghaddam, M. (2013) · ACM Transactions on Algorithms · doi:10.1145/2500121 · Cited by 87
Fast greedy algorithms in mapreduce and streaming
Kumar, R., Moseley, B., Vassilvitskii, S., & Vattani, A. (2013) · ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) · doi:10.1145/2486159.2486168 · Cited by 90
Scheduling algorithms for multi-carrier wireless data systems
Andrews, M., & Zhang, L. (2007) · ACM Annual International Conference on Mobile Computing and Networking (MobiCom) · doi:10.1145/1287853.1287856 · Cited by 89
Maximizing monotone submodular functions over the integer lattice
Soma, T., & Yoshida, Y. (2018) · Mathematical Programming · doi:10.1007/s10107-018-1324-y · Cited by 86
Dai, H., Ma, Q., Wu, X., Chen, G., Yau, D. K. Y., Tang, S., Li, X., & Tian, C. (2018) · IEEE Transactions on Mobile Computing · doi:10.1109/tmc.2018.2887381 · Cited by 83
Accelerating DNN Inference With Reliability Guarantee in Vehicular Edge Computing
Liu, K., Liu, C., Yan, G., Lee, V. C. S., & Cao, J. (2023) · IEEE/ACM Transactions on Networking · doi:10.1109/tnet.2023.3279512 · Cited by 86
Submodular Maximization by Simulated Annealing
Gharan, S. O., & Vondrák, J. (2011) · ACM-SIAM Symposium on Discrete Algorithms (SODA) · doi:10.1137/1.9781611973082.83 · Cited by 82
A Tight Combinatorial Algorithm for Submodular Maximization Subject to a Matroid Constraint
Filmus, Y., & Ward, J. (2012) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2012.55 · Cited by 72
Information theoretic sensor management
Fisher, J. S., Willsky, A. S., & Williams, J. (2007) · Cited by 72
Distributed Submodular Maximization With Limited Information
Gharesifard, B., & Smith, S. L. (2016) · Proceedings of the ... American Control Conference/Proceedings of the American Control Conference · doi:10.1109/acc.2016.7525053 · Cited by 67
Constrained Submodular Maximization via a Nonsymmetric Technique
Buchbinder, N., & Feldman, M. (2019) · Mathematics of Operations Research · doi:10.1287/moor.2018.0955 · Cited by 70
Streaming Algorithms for Submodular Function Maximization
Chekuri, C., Gupta, S., & Quanrud, K. (2015) · Lecture notes in computer science · doi:10.1007/978-3-662-47672-7_26 · Cited by 68
Maximizing Non-Monotone Submodular Functions
Feige, U., Mirrokni, V., & Vondrák, J. (2007) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2007.29 · Cited by 94
An Auction Approach to Resource Allocation in Uplink OFDMA Systems
Yang, K., Prasad, N., & Wang, X. (2009) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2009.2025794 · Cited by 66
Boley, M., Mampaey, M., Kang, B., Tokmakov, P., & Wrobel, S. (2013) · doi:10.1145/2501511.2501517 · Cited by 65
A Stochastic Probing Problem with Applications
Gupta, A., & Nagarajan, V. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-36694-9_18 · Cited by 65
Low-Complexity Beam Allocation for Switched-Beam Based Multiuser Massive MIMO Systems
Wang, J., Zhu, H., Dai, L., Gomes, N. J., & Wang, J. (2016) · IEEE Transactions on Wireless Communications · doi:10.1109/twc.2016.2613517 · Cited by 65
A Canonical Representation of Simple Plant Location Problems and Its Applications
Cornuéjols, G., Nemhauser, G. L., & Wolsey, L. A. (1980) · SIAM Journal on Algebraic and Discrete Methods · doi:10.1137/0601030 · Cited by 63
Self-citationChan, C. W., & Farias, V. F. (2009) · Mathematics of Operations Research · doi:10.1287/moor.1080.0364 · Cited by 63
A Survey on Influence Maximization: From an ML-Based Combinatorial Optimization
Li, Y., Gao, H., Gao, Y., Guo, J., & Wu, W. (2023) · ACM Transactions on Knowledge Discovery from Data · doi:10.1145/3604559 · Cited by 73
Submodular Secretary Problem and Extensions
Bateni, M., Hajiaghayi, M., & Zadimoghaddam, M. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-15369-3_4 · Cited by 58
Maximizing Stochastic Monotone Submodular Functions
Asadpour, A., & Nazerzadeh, H. (2015) · Management Science · doi:10.1287/mnsc.2015.2254 · Cited by 61
Qu, G., Brown, D., & Li, N. (2019) · Automatica · doi:10.1016/j.automatica.2019.03.007 · Cited by 60
Online submodular welfare maximization: Greedy is optimal
Kapralov, M., Post, I., & Vondrák, J. (2013) · ACM-SIAM Symposium on Discrete Algorithms (SODA) · doi:10.1137/1.9781611973105.88 · Cited by 59
Multi-robot Coordination and Planning in Uncertain and Adversarial Environments
Zhou, L., & Tokekar, P. (2021) · Current Robotics Reports · doi:10.1007/s43154-021-00046-5 · Cited by 62
Directed submodularity, ditroids and directed submodular flows
Qi, L. (1988) · Mathematical Programming · doi:10.1007/bf01589420 · Cited by 57
Welfare maximization and the supermodular degree
Feige, U., & Izsak, R. (2013) · Conference on Innovations in Theoretical Computer Science · doi:10.1145/2422436.2422466 · Cited by 56
Near Optimal Charging and Scheduling Scheme for Stochastic Event Capture with Rechargeable Sensors
Dai, H., Jiang, L., Wu, X., Yau, D. K. Y., Chen, G., & Tang, S. (2013) · IEEE International Conference on Mobile Ad-Hoc and Sensor Systems (MASS) · doi:10.1109/mass.2013.60 · Cited by 55
Almost optimal virtual machine placement for traffic intense data centers
Cohen, R., Lewin-Eytan, L., Naor, J. S., & Raz, D. (2013) · IEEE Conference on Computer Communications (INFOCOM) · doi:10.1109/infcom.2013.6566794 · Cited by 54
Efficient Online Multi-robot Exploration via Distributed Sequential Greedy Assignment
Corah, M., & Michael, N. (2017) · Robotics: Science and Systems · doi:10.15607/rss.2017.xiii.070 · Cited by 54
IMPC: Influence maximization based on multi-neighbor potential in community networks
Shang, J., Wu, H., Zhou, S., Zhong, J., Feng, Y., & Qiang, B. (2018) · Physica A Statistical Mechanics and its Applications · doi:10.1016/j.physa.2018.08.045 · Cited by 54
A New Framework for Distributed Submodular MaximizationPreprint
Barbosa, R. D. P., Ene, A. R., Nguyễn, H. L., & Ward, J. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1507.03719 · Cited by 54
Approximation for maximizing monotone non-decreasing set functions with a greedy method
Wang, Z., Moran, B., Wang, X., & Pan, Q. (2014) · Journal of Combinatorial Optimization · doi:10.1007/s10878-014-9707-3 · Cited by 53
On leader selection for performance and controllability in multi-agent systems
Clark, A., Bushnell, L. G., & Poovendran, R. (2012) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2012.6426973 · Cited by 52
Maximizing Charging Satisfaction of Smartphone Users via Wireless Energy Transfer
Xu, W., Liang, W., Peng, J., Liu, Y., & Wang, Y. (2016) · IEEE Transactions on Mobile Computing · doi:10.1109/tmc.2016.2577585 · Cited by 52
Tight Approximation Algorithms for Maximum Separable Assignment Problems
Fleischer, L., Goemans, M. X., Mirrokni, V. S., & Sviridenko, M. (2011) · Mathematics of Operations Research · doi:10.1287/moor.1110.0499 · Cited by 65
Making your interests follow you on twitter
Marco Pennacchiotti, B., Silvestri, F., Vahabi, H., & Venturini, R. (2012) · ACM International Conference on Information and Knowledge Management (CIKM) · doi:10.1145/2396761.2396786 · Cited by 51
Learning mixtures of submodular shells with application to document summarization
Lin, H. Z., & Bilmes, J. (2012) · Cited by 51
Max-Sum Diversification, Monotone Submodular Functions, and Dynamic Updates
Borodin, A., Jain, A., Lee, H. C., & Ye, Y. (2017) · ACM Transactions on Algorithms · doi:10.1145/3086464 · Cited by 50
Simultaneous Optimization of Sensor Placements and Balanced Schedules
Krause, A., Rajagopal, R., Gupta, A., & Guestrin, C. (2011) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2011.2164010 · Cited by 49
Exploiting submodularity to quantify near-optimality in multi-agent coverage problems
Sun, X., Cassandras, C. G., & Meng, X. (2018) · Automatica · doi:10.1016/j.automatica.2018.11.020 · Cited by 49
Next-Best-View planning for surface reconstruction of large-scale 3D environments with multiple UAVs
Hardouin, G., Moras, J., Morbidi, F., Marzat, J., & Mouaddib, E. M. (2020) · IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) · doi:10.1109/iros45743.2020.9340897 · Cited by 49
Near optimal multi-application allocation in shared sensor networks
Xu, Y., Saifullah, A. M., Chen, Y., Lu, C., & Bhattacharya, S. (2010) · ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc) · doi:10.1145/1860093.1860118 · Cited by 48
Weighted Coverage based Reviewer Assignment
Kou, N. M., Leong Hou, U., Mamoulis, N., & Gong, Z. (2015) · ACM SIGMOD International Conference on Management of Data (SIGMOD) · doi:10.1145/2723372.2723727 · Cited by 48
On maximizing a monotone k -submodular function subject to a matroid constraint
Sakaue, S. (2017) · Discrete Optimization · doi:10.1016/j.disopt.2017.01.003 · Cited by 48
Approximation Algorithms for the Generalized Team Orienteering Problem and its Applications
Xu, W., Liang, W., Xu, Z., Peng, J., Peng, D., Liu, T., Jia, X., & Das, S. K. (2020) · IEEE/ACM Transactions on Networking · doi:10.1109/tnet.2020.3027434 · Cited by 48
Symmetry and Approximability of Submodular Maximization Problems
Vondrák, J. (2009) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2009.24 · Cited by 48
Optimal approximation for submodular and supermodular optimization with bounded curvature
Sviridenko, M. I., Vondrák, J., & Ward, J. (2014) · ACM-SIAM Symposium on Discrete Algorithms (SODA) · doi:10.1137/1.9781611973730.76 · Cited by 47
Robust Multi-Robot Active Target Tracking Against Sensing and Communication Attacks
Zhou, L., & Kumar, V. (2023) · IEEE Transactions on Robotics · doi:10.1109/tro.2022.3233341 · Cited by 46
Buyback Problem - Approximate Matroid Intersection with Cancellation Costs
Varadaraja, A. B. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-22006-7_32 · Cited by 45
Fixed-Charge Facility Location Problems
Fernández, E., & Landete, M. (2015) · Springer eBooks · doi:10.1007/978-3-319-13111-5_3 · Cited by 45
Hub Location as the Minimization of a Supermodular Set Function
Contreras, I., & Fernández, E. (2014) · Operations Research · doi:10.1287/opre.2014.1263 · Cited by 43
Solving Packing Integer Programs via Randomized Rounding with Alterations
Bansal, N., Korula, N., Nagarajan, V., & Srinivasan, A. (2012) · Theory of Computing · doi:10.4086/toc.2012.v008a024 · Cited by 43
An Accelerated Sequential Algorithm for Producing D -Optimal Designs
Robertazzi, T. G., & Schwartz, S. C. (1989) · SIAM Journal on Scientific and Statistical Computing · doi:10.1137/0910022 · Cited by 42
Server Placement for Edge Computing: A Robust Submodular Maximization Approach
Qu, Y., Wang, L., Dai, H., Wang, W., Dong, C., Wu, F., & Guo, S. (2021) · IEEE Transactions on Mobile Computing · doi:10.1109/tmc.2021.3136868 · Cited by 41
Metadata
- Authors
- Fisher, M. L., Nemhauser, G. L., & Wolsey, L. A.
- Affiliations
- University of Pennsylvania (US)
- UCLouvain (BE)
- Venue
- Mathematical Programming Studies
- Publisher
- Springer Berlin Heidelberg
- Published
- 1978
- Pages
- 73-87
- ISSN
- 0303-3929 (ISSN-L)
- OpenAlex
- W2757107770
- Cited by
- 589
- References
- 9
- Citations by year
- 2026: 15 · 2025: 28 · 2024: 30 · 2023: 45 · 2022: 57 · 2021: 35 · 2020: 53 · 2019: 40 · 2018: 37 · 2017: 35 · 2016: 27 · 2015: 35 · 2014: 20 · 2013: 29 · 2012: 18
- FWCI
- 7.98
- Type
- book chapter
- Language
- en
- Open access
- closed
- Locations
- Mathematical programming studies (publishedVersion)
- Digital Access to Libraries (Université catholique de Louvain (UCL), l'Université de Namur (UNamur) and the Université Saint-Louis (USL-B)) (submittedVersion)
- Topics
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Complexity and Algorithms in Graphs
- Physical Sciences › Mathematics › Discrete Mathematics and Combinatorics › Advanced Combinatorial Mathematics
- Social Sciences › Economics, Econometrics and Finance › Economics and Econometrics › Game Theory and Voting Systems
- Keywords
- submodular functions, maximization, approximation algorithms, greedy algorithm, linear programming relaxation, matroid intersection, worst-case bounds, nondecreasing functions
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
