NDLI: On Testing Convexity and Submodularity

Please wait, while we are loading the content...

On Testing Convexity and Submodularity

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	Ron, Dana Parnas, Michal Rubinfeld, Ronitt
Copyright Year	2003
Abstract	Convex and submodular functions play an important role in many applications, and in particular in combinatorial optimization. Here we study two special cases: convexity in one dimension and submodularity in two dimensions. The latter type of functions are equivalent to the well-known Monge matrices. A matrix $V = \{v_{i,j}\}_{i,j=0}^{i=n_1,j=n_2}$ is called a Monge matrix if for every $0 \leq i < i' \leq n_1$ and $0 \leq j < j' \leq n_2$ we have $v_{i,j}+v_{i',j'} \le v_{i,j'}+v_{i',j}$. If inequality holds in the opposite direction, then V is an inverse Monge matrix (supermodular function). Many problems, such as the traveling salesperson problem and various transportation problems, can be solved more efficiently if the input is a Monge matrix.In this work we present testing algorithms for the above properties. A testing algorithm for a predetermined property $\cal P$ is given query access to an unknown function f and a distance parameter $\epsilon$. The algorithm should accept f with high probability if it has the property $\cal P$ and reject it with high probability if more than an $\epsilon$-fraction of the function values should be modified so that f obtains the property. Our algorithm for testing whether a 1-dimensional function $f:[n] \rightarrow \mathbb{R}$ is convex (concave) has query complexity and running time of $O\left((\log n) /\epsilon\right)$. Our algorithm for testing whether an n1 n2 matrix V is a Monge (inverse Monge) matrix has query complexity and running time of $O\left((\log n_1\cdot\log n_2) /\epsilon\right)$.
Starting Page	1158
Ending Page	1184
Page Count	27
File Format	PDF
ISSN	00975397
DOI	10.1137/S0097539702414026
e-ISSN	10957111
Journal	SIAM Journal on Computing (SMJCAT)
Issue Number	5
Volume Number	32
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2003-01-01
Access Restriction	Subscribed
Subject Keyword	convex functions randomized algorithms Randomized algorithms Approximation algorithms property testing approximation algorithms Monge matrices Analysis of algorithms Functional inequalities, including subadditivity, convexity, etc.
Content Type	Text
Resource Type	Article
Subject	Mathematics Computer Science

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in