An Approximation Algorithm To The File Allocation Problem In Computer Networks

Summary: O(N^3) approximation algorithm for file allocation in arbitrary networks using marginal-savings, marginal-cost and incremental-benefit rules. Proves an analytical worst-case approximation bound that generalizes Johnson–Chvátal set-cover results and compares to heuristics/IP. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 661
Venue: PODS
Year: 1983
Pagerank: -
Overall Rank: 14,503 | 0.50%
DOI: 10.1145/588058.588087

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Kowtha Murthy
2. John Kan (Wang Research Laboratories)
3. M S Krishnamoorthy (Rensselaer Polytechnic Institute)

BibTeX Citation

@inproceedings{murthy_pods83,
        address = {New York, NY, USA},
        series = {{PODS} '83},
        title = {{AN APPROXIMATION ALGORITHM TO THE FILE ALLOCATION PROBLEM IN COMPUTER NETWORKS}},
        url = {https://dl.acm.org/doi/10.1145/588058.588087},
        doi = {10.1145/588058.588087},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Murthy, Kowtha and Kan, John and Krishnamoorthy, M S},
        year = {1983}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 0 of 0 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,698	Tight Trade-offs for the Maximum k-Coverage Problem in the General Streaming Model	2019	PODS
2	6,901	Near-Optimal Algorithms for Shared Filter Evaluation in Data Stream Systems	2008	SIGMOD
3	9,402	Approximation Algorithms for Co-Clustering	2008	PODS
4	6,460	Reading a Set of Disk Pages	1993	VLDB
5	6,683	Efficient Algorithms for Optimal Location Queries in Road Networks	2014	SIGMOD
6	8,932	Noticeable Network Delay Minimization via Node Upgrades	2018	VLDB
7	9,094	Algorithms for Data Migration with Cloning	2003	PODS
8	7,688	Incremental File Reorganization Schemes	1985	VLDB
9	13,256	File Allocation in Distributed Databases with Interaction between Files	1983	VLDB
10	13,272	An Approximation Algorithm For A File-Allocation Problem In A Hierarchical Distributed System.	1980	SIGMOD