More Web Proxy on the site http://driver.im/

research-article

Reconfiguration Problems on Submodular Functions

Authors:

Tatsuya MatsuokaAuthors Info & Claims

WSDM '22: Proceedings of the Fifteenth ACM International Conference on Web Search and Data Mining

Pages 764 - 774

https://doi.org/10.1145/3488560.3498382

Published: 15 February 2022 Publication History

Abstract

\emphReconfiguration problems require finding a step-by-step transformation between a pair of feasible solutions for a particular problem. The primary concern in Theoretical Computer Science has been revealing their computational complexity for classical problems.

This paper presents an initial study on reconfiguration problems derived from a submodular function, which has more of a flavor of Data Mining. Our submodular reconfiguration problems request to find a solution sequence connecting two input solutions such that each solution has an objective value above a threshold in a submodular function $f: 2^[n] \to \mathbbR _+$ and is obtained from the previous one by applying a simple transformation rule. We formulate three reconfiguration problems: Monotone Submodular Reconfiguration (MSReco), which applies to influence maximization, and two versions of Unconstrained Submodular Reconfiguration (USReco), which apply to determinantal point processes. Our contributions are summarized as follows: \beginitemize \item We prove that MSReco and USReco are both PSPACE-complete. \item We design a $\frac1 2 $-approximation algorithm for MSReco and a $\frac1 n $-approximation algorithm for (one version of) USReco. \item We devise inapproximability results that approximating the optimum value of MSReco within a $(1-\frac1+ε n^2 )$-factor is PSPACE-hard, and we cannot find a $(\frac5 6 +ε)$-approximation for USReco. \item We conduct numerical study on the reconfiguration version of influence maximization and determinantal point processes using real-world social network and movie rating data. \enditemize

Supplementary Material

MP4 File (WSDM22-fp097.mp4)

Presentation video.

Download
110.69 MB

References

[1]

Gediminas Adomavicius and Jingjing Zhang. 2012. Stability of recommendation algorithms. ACM Trans. Inf. Syst., Vol. 30, 4 (2012), 23:1--23:31.

Digital Library

[2]

Akhil Arora, Sainyam Galhotra, and Sayan Ranu. 2017. Debunking the Myths of Influence Maximization: An In-Depth Benchmarking Study. In SIGMOD . 651--666.

[3]

Sanjeev Arora and Boaz Barak. 2009. Computational Complexity: A Modern Approach .Cambridge University Press.

Digital Library

[4]

Masataro Asai and Alex Fukunaga. 2016. Tiebreaking strategies for A* search: How to explore the final frontier. In AAAI . 673--679.

[5]

Paul Bonsma and Luis Cereceda. 2009. Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances. Theor. Comput. Sci., Vol. 410, 50 (2009), 5215--5226.

Digital Library

[6]

Christian Borgs, Michael Brautbar, Jennifer Chayes, and Brendan Lucier. 2014. Maximizing Social Influence in Nearly Optimal Time. In SODA. 946--957.

[7]

Alexei Borodin and Eric M. Rains. 2005. Eynard-Mehta theorem, Schur process, and their Pfaffian analogs. J. Stat. Phys., Vol. 121, 3--4 (2005), 291--317.

[8]

Christos Boutsidis and Efstratios Gallopoulos. 2008. SVD based initialization: A head start for nonnegative matrix factorization. Pattern Recognit., Vol. 41, 4 (2008), 1350--1362.

Digital Library

[9]

Niv Buchbinder and Moran Feldman. 2018a. Deterministic algorithms for submodular maximization problems. ACM Trans. Algorithms, Vol. 14, 3 (2018), 1--20.

Digital Library

[10]

Niv Buchbinder and Moran Feldman. 2018b. Submodular Functions Maximization Problems. In Handbook of Approximation Algorithms and Metaheuristics. Chapman and Hall/CRC, 771--806.

[11]

Niv Buchbinder, Moran Feldman, Joseph Seffi, and Roy Schwartz. 2015. A tight linear time (1/2)-approximation for unconstrained submodular maximization. SIAM J. Comput., Vol. 44, 5 (2015), 1384--1402.

Digital Library

[12]

Jean Cardinal, Erik D. Demaine, David Eppstein, Robert A. Hearn, and Andrew Winslow. 2020. Reconfiguration of satisfying assignments and subset sums: Easy to find, hard to connect. Theor. Comput. Sci., Vol. 806 (2020), 332--343.

Digital Library

[13]

Laming Chen, Guoxin Zhang, and Eric Zhou. 2018. Fast greedy MAP inference for determinantal point process to improve recommendation diversity. In NeurIPS. 5622--5633.

[14]

Wei Chen, Chi Wang, and Yajun Wang. 2010. Scalable Influence Maximization for Prevalent Viral Marketing in Large-Scale Social Networks. In KDD. 1029--1038.

[15]

Michele Conforti and Gérard Cornuéjols. 1984. Submodular set functions, matroids and the greedy algorithm: Tight worst-case bounds and some generalizations of the Rado-Edmonds theorem. Discrete Appl. Math., Vol. 7, 3 (1984), 251--274.

[16]

Stephen A. Cook. 1971. The complexity of theorem-proving procedures. In STOC. 151--158.

[17]

Pedro Domingos and Matt Richardson. 2001. Mining the Network Value of Customers. In KDD. 57--66.

[18]

Uriel Feige. 1998. A threshold of ln n for approximating set cover. J. ACM, Vol. 45, 4 (1998), 634--652.

Digital Library

[19]

Uriel Feige, Vahab S. Mirrokni, and Jan Vondrák. 2011. Maximizing non-monotone submodular functions. SIAM J. Comput., Vol. 40, 4 (2011), 1133--1153.

Digital Library

[20]

Michael R. Garey and David S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness .W. H. Freeman.

Digital Library

[21]

Jennifer Gillenwater, Alex Kulesza, and Ben Taskar. 2012. Near-optimal MAP inference for determinantal point processes. In NIPS . 2735--2743.

[22]

Jacob Goldenberg, Barak Libai, and Eitan Muller. 2001. Talk of the network: A complex systems look at the underlying process of word-of-mouth. Mark. Lett., Vol. 12, 3 (2001), 211--223.

[23]

Parikshit Gopalan, Phokion G. Kolaitis, Elitza Maneva, and Christos H. Papadimitriou. 2009. The connectivity of Boolean satisfiability: computational and structural dichotomies. SIAM J. Comput., Vol. 38, 6 (2009), 2330--2355.

Digital Library

[24]

F. Maxwell Harper and Joseph A. Konstan. 2015. The MovieLens datasets: History and context. ACM Trans. Interact. Intell. Syst., Vol. 5, 4 (2015), 1--19.

Digital Library

[25]

Peter E. Hart, Nils J. Nilsson, and Bertram Raphael. 1968. A formal basis for the heuristic determination of minimum cost paths. IEEE Trans. Syst. Sci. Cybern., Vol. 4, 2 (1968), 100--107.

[26]

Robert A. Hearn and Erik D. Demaine. 2005. PSPACE-Completeness of Sliding-Block Puzzles and Other Problems through the Nondeterministic Constraint Logic Model of Computation. Theor. Comput. Sci., Vol. 343, 1--2 (2005), 72--96.

Digital Library

[27]

Takehiro Ito and Erik D. Demaine. 2014. Approximability of the subset sum reconfiguration problem. J. Comb. Optim., Vol. 28, 3 (2014), 639--654.

Digital Library

[28]

Takehiro Ito, Erik D. Demaine, Nicholas J.A. Harvey, Christos H. Papadimitriou, Martha Sideri, Ryuhei Uehara, and Yushi Uno. 2011. On the complexity of reconfiguration problems. Theor. Comput. Sci., Vol. 412, 12--14 (2011), 1054--1065.

Digital Library

[29]

Takehiro Ito, Hiroyuki Nooka, and Xiao Zhou. 2016. Reconfiguration of vertex covers in a graph. IEICE Trans. Inf. & Syst., Vol. 99, 3 (2016), 598--606.

[30]

Rishabh K. Iyer, Stefanie Jegelka, and Jeff A. Bilmes. 2013. Curvature and optimal algorithms for learning and minimizing submodular functions. In NIPS . 2742--2750.

[31]

Matthew Johnson, Dieter Kratsch, Stefan Kratsch, Viresh Patel, and Daniël Paulusma. 2016. Finding shortest paths between graph colourings. Algorithmica, Vol. 75, 2 (2016), 295--321.

Digital Library

[32]

Wm Woolsey Johnson and William Edward Story. 1879. Notes on the “15” puzzle. Am. J. Math., Vol. 2, 4 ( 1879), 397--404.

[33]

Marcin Kami'nski, Paul Medvedev, and Martin Milanivc. 2012. Complexity of independent set reconfigurability problems. Theor. Comput. Sci., Vol. 439 (2012), 9--15.

Digital Library

[34]

Richard M. Karp. 1972. Reducibility among combinatorial problems. In Complexity of Computer Computations . 85--103.

[35]

David Kempe, Jon Kleinberg, and É va Tardos. 2003. Maximizing the Spread of Influence through a Social Network. In KDD. 137--146.

[36]

Andreas Krause and Daniel Golovin. 2014. Submodular Function Maximization. In Tractability: Practical Approaches to Hard Problems. 71--104.

[37]

Andreas Krause, Ajit Paul Singh, and Carlos Guestrin. 2008. Near-optimal sensor placements in Gaussian processes: Theory, efficient algorithms and empirical studies. J. Mach. Learn. Res., Vol. 9 (2008), 235--284.

Digital Library

[38]

Alex Kulesza and Ben Taskar. 2012. Determinantal Point Processes for Machine Learning. Found. Trends Mach. Learn., Vol. 5, 2--3 (2012), 123--286.

[39]

Jérôme Kunegis. 2013. KONECT -- The Koblenz Network Collection. In WWW Companion . 1343--1350.

[40]

Jure Leskovec, Jon Kleinberg, and Christos Faloutsos. 2007 a. Graph Evolution: Densification and Shrinking Diameters. ACM Trans. Knowl. Discov. Data, Vol. 1, 1 (2007), 2.

Digital Library

[41]

Jure Leskovec, Andreas Krause, Carlos Guestrin, Christos Faloutsos, Jeanne VanBriesen, and Natalie Glance. 2007 b. Cost-effective Outbreak Detection in Networks. In KDD. 420--429.

[42]

Leonid Anatolevich Levin. 1973. Universal sequential search problems. Probl. Peredachi Inf., Vol. 9, 3 (1973), 115--116.

[43]

David Lichtenstein and Michael Sipser. 1980. Go is polynomial-space hard. J. ACM, Vol. 27, 2 (1980), 393--401.

Digital Library

[44]

Hui Lin and Jeff Bilmes. 2011. A class of submodular functions for document summarization. In ACL-HLT . 510--520.

[45]

Grigorios Loukides, Robert Gwadera, and Shing-Wan Chang. 2020. Overexposure-aware influence maximization. ACM Trans. Internet Technol., Vol. 20, 4 (2020), 1--31.

Digital Library

[46]

László Lovász. 1983. Submodular Functions and Convexity. In Mathematical Programming -- The State of the Art. 235--257.

[47]

Odile Macchi. 1975. The coincidence approach to stochastic point processes. Adv. Appl. Probab., Vol. 7, 1 (1975), 83--122.

[48]

Baharan Mirzasoleiman, Ashwinkumar Badanidiyuru, and Amin Karbasi. 2016. Fast constrained submodular maximization: Personalized data summarization. In ICML . 1358--1367.

[49]

Amer Mouawad. 2015. On Reconfiguration Problems: Structure and Tractability . Ph.,D. Dissertation. University of Waterloo.

[50]

George L. Nemhauser and Laurence A. Wolsey. 1978. Best algorithms for approximating the maximum of a submodular set function. Math. Oper. Res., Vol. 3, 3 (1978), 177--188.

Digital Library

[51]

George L. Nemhauser, Laurence A. Wolsey, and Marshall L. Fisher. 1978. An analysis of the approximations for maximizing submodular set functions. Math. Program., Vol. 14 (1978), 265--294.

Digital Library

[52]

Naomi Nishimura. 2018. Introduction to Reconfiguration. Algorithms, Vol. 11, 4 (2018), 52.

[53]

Naoto Ohsaka. 2020. The solution distribution of influence maximization: A high-level experimental study on three algorithmic approaches. In SIGMOD .

[54]

Naoto Ohsaka, Takuya Akiba, Yuichi Yoshida, and Ken-ichi Kawarabayashi. 2016. Dynamic Influence Analysis in Evolving Networks. Proc. VLDB Endow., Vol. 9, 12 (2016), 1077--1088.

Digital Library

[55]

Judea Pearl. 1984. Heuristics: Intelligent Search Strategies for Computer Problem Solving. (1984).

Digital Library

[56]

Walter J. Savitch. 1970. Relationships between nondeterministic and deterministic tape complexities. J. Comput. Syst. Sci., Vol. 4, 2 (1970), 177--192.

Digital Library

[57]

Alexander Schrijver. 2003. Combinatorial Optimization: Polyhedra and Efficiency .Springer Science & Business Media.

[58]

Dravyansh Sharma, Ashish Kapoor, and Amit Deshpande. 2015. On greedy maximization of entropy. In ICML. 1330--1338.

[59]

Youze Tang, Xiaokui Xiao, and Yanchen Shi. 2014. Influence Maximization: Near-Optimal Time Complexity Meets Practical Efficiency. In SIGMOD. 75--86.

Digital Library

[60]

Jan van den Heuvel. 2013. The complexity of change. In Surveys in Combinatorics 2013 . Vol. 409. 127--160.

[61]

Saúl Vargas and Pablo Castells. 2011. Rank and relevance in novelty and diversity metrics for recommender systems. In RecSys . 109--116.

[62]

Jan Vondrák. 2010. Submodularity and Curvature: The Optimal Algorithm (Combinatorial Optimization and Discrete Algorithms). RIMS Kôkyûroku Bessatsu 23 (2010), 253--266.

[63]

Mark Wilhelm, Ajith Ramanathan, Alexander Bonomo, Sagar Jain, Ed H. Chi, and Jennifer Gillenwater. 2018. Practical diversified recommendations on YouTube with determinantal point processes. In CIKM . 2165--2173.

[64]

Jin-ge Yao, Feifan Fan, Wayne Xin Zhao, Xiaojun Wan, Edward Y. Chang, and Jianguo Xiao. 2016. Tweet Timeline Generation with Determinantal Point Processes. In AAAI. 3080--3086.

Cited By

Banihashem KBiabani LGoudarzi SHajiaghayi MJabbarzade PMonemizadeh MKrause ABrunskill ECho KEngelhardt BSabato SScarlett J(2023)Dynamic constrained submodular optimization with polylogarithmic update timeProceedings of the 40th International Conference on Machine Learning10.5555/3618408.3618479(1660-1691)Online publication date: 23-Jul-2023
https://dl.acm.org/doi/10.5555/3618408.3618479

Index Terms

Reconfiguration Problems on Submodular Functions
1. Information systems
  1. Information systems applications
    1. Data mining
2. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis

Recommendations

Maximizing Non-monotone Submodular Functions

Submodular maximization generalizes many important problems including Max Cut in directed and undirected graphs and hypergraphs, certain constraint satisfaction problems, and maximum facility location problems. Unlike the problem of minimizing ...
Symmetry and Approximability of Submodular Maximization Problems

A number of recent results on optimization problems involving submodular functions have made use of the multilinear relaxation of the problem. These results hold typically in the value oracle model, where the objective function is accessible via a black box ...
On the Parameterized Complexity of Reconfiguration Problems

We present the first results on the parameterized complexity of reconfiguration problems, where a reconfiguration variant of an optimization problem $$\mathcal {Q}$$Q takes as input two feasible solutions S and T and determines if there is a sequence of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

WSDM '22: Proceedings of the Fifteenth ACM International Conference on Web Search and Data Mining

February 2022

1690 pages

ISBN:9781450391320

DOI:10.1145/3488560

General Chairs:
K. Selcuk Candan
Arizona State University, USA
,
Huan Liu
Arizona State University, USA
,
Program Chairs:
Leman Akoglu
Carnegie Mellon University, USA
,
Xin Luna Dong
Meta Platforms, Inc. (former Facebook), USA
,
Jiliang Tang
Michigan State University, USA

Copyright © 2022 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 15 February 2022

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

WSDM '22

Sponsor:

WSDM '22: The Fifteenth ACM International Conference on Web Search and Data Mining

February 21 - 25, 2022

AZ, Virtual Event, USA

Acceptance Rates

Overall Acceptance Rate 498 of 2,863 submissions, 17%

Upcoming Conference

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
111
Total Downloads

Downloads (Last 12 months)21
Downloads (Last 6 weeks)0

Reflects downloads up to 14 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Banihashem KBiabani LGoudarzi SHajiaghayi MJabbarzade PMonemizadeh MKrause ABrunskill ECho KEngelhardt BSabato SScarlett J(2023)Dynamic constrained submodular optimization with polylogarithmic update timeProceedings of the 40th International Conference on Machine Learning10.5555/3618408.3618479(1660-1691)Online publication date: 23-Jul-2023
https://dl.acm.org/doi/10.5555/3618408.3618479

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents