Article

Upgrading arc problem with budget constraint

Author:

Li ZhangAuthors Info & Claims

ACMSE '05 vol 1: Proceedings of the 43rd annual ACM Southeast Conference - Volume 1

Pages 150 - 152

https://doi.org/10.1145/1167350.1167396

Published: 18 March 2005 Publication History

Get Access

Abstract

Upgrading arcs are often used in transportation and telecommunication systems. In a real world situation, upgrading an arc between a pair of nodes corresponds to using a rapid mode of transit, such as using a plane instead of a truck between a pair of cities in a transportation network or using a higher speed cable between a pair of servers in a telecommunication network. These upgrades decrease transportation times through the network and can be critical in achieving delivery deadlines. This paper introduces and analyzes the upgrading arc problem with budget constraint. We show that this problem is NP-Complete in general and present several polynomially solvable cases.

References

[1]

Campbell, A. M., Lowe, T. J. and Zhang, L. Upgrading arcs to minimize the maximum travel time in a network. Working paper, 2004.]]

Google Scholar

[2]

Campbell, J. F., Ernst, A. and Krishnamoorthy, M. Facility location: applications and theory. Springer-Verlag, 2002.]]

Google Scholar

[3]

Campbell, J. F., Ernst, A. and Krishnamoorthy, M. Hub arc location problems: part 1 -- introduction and results. Submitted to Management Science, 2004.]]

Digital Library

Google Scholar

[4]

Campbell, J. F., Ernst, A. and Krishnamoorthy, M. Hub arc location problems: part 2 -- formulations and optimal algorithms. Submitted to Management Science, 2004.]]

Google Scholar

[5]

Chan, P. K. Algorithms for library-specific sizing of combinatorial logic. In Proceedings of the 27th DAC Conference, 1990, 353--356.]]

Digital Library

Google Scholar

[6]

Garey, M. R. and Johnson, D. S. Computer and Intractability. A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, New York, 1979.]]

Digital Library

Google Scholar

[7]

Iyer, A. V. and Ratliff, H. D. Accumulation point location on tree networks for guaranteed time distribution. Management Science, 1990, 36(8):958--969.]]

Digital Library

Google Scholar

[8]

Kara, B. Y. and Tansel, B. C. On the single-assignment p-hub center problem. European Journal of Operational Research, 2000, 125(3):648--655.]]

Crossref

Google Scholar

[9]

McGreer, P., Brayton, R., Rudell, R. and Sangiovanni-Vincentelli, A. Extended stuck-fault testability for combinatorial networks. In Proceedings of the 6th MIT Conference on Advanced Research in VLSI, April 1990.]]

Digital Library

Google Scholar

[10]

O'Kelly, M. E. and Miller, H. J. A quadratic integer program for the location of interacting hub facilities. European Journal of Operational Research, 1987, 32:393--404.]]

Crossref

Google Scholar

[11]

O'Kelly, M. E. and Miller, H. J. Solution strategies for the single facility minimax hub location problem. Papers in Regional Science: The Journal of the RSAI, 1991, 70:367--380.]]

Crossref

Google Scholar

[12]

Paik, D. and Sahni, S. Network upgrading problems. Networks, 1995, 26:45--58.]]

Crossref

Google Scholar

[13]

Zhang, L. The p-hub center allocation problem and the q-upgrading arc problem. Ph.D. thesis, The University of Iowa, Iowa, 2004.]]

Google Scholar

Cited By

View all

Lin YMouratidis K(2015)Best upgrade plans for single and multiple source-destination pairsGeoinformatica10.1007/s10707-014-0219-119:2(365-404)Online publication date: 1-Apr-2015
https://dl.acm.org/doi/10.1007/s10707-014-0219-1
Lin YMouratidis K(2013)Best Upgrade Plans for Large Road NetworksProceedings of the 13th International Symposium on Advances in Spatial and Temporal Databases - Volume 809810.5555/2960717.2960734(223-240)Online publication date: 21-Aug-2013
https://dl.acm.org/doi/10.5555/2960717.2960734
Lin YMouratidis K(2013)Best Upgrade Plans for Large Road NetworksAdvances in Spatial and Temporal Databases10.1007/978-3-642-40235-7_13(223-240)Online publication date: 2013
https://doi.org/10.1007/978-3-642-40235-7_13
Show More Cited By

Recommendations

Complexities of some interesting problems on spanning trees

This paper deals with the complexity issues of some new interesting spanning tree problems. Here we define some new spanning tree problems by imposing various constraints and restrictions on graph parameters and present relevant results. Also we ...
Limits of minimum circuit size problem as oracle
CCC '16: Proceedings of the 31st Conference on Computational Complexity

The Minimum Circuit Size Problem (MCSP) is known to be hard for statistical zero knowledge via a BPP-Turing reduction (Allender and Das, 2014), whereas establishing NP-hardness of MCSP via a polynomial-time many-one reduction is difficult (Murray and ...
On the (non) NP-hardness of computing circuit complexity
CCC '15: Proceedings of the 30th Conference on Computational Complexity

The Minimum Circuit Size Problem (MCSP) is: given the truth table of a Boolean function f and a size parameter k, is the circuit complexity of f at most k? This is the definitive problem of circuit synthesis, and it has been studied since the 1950s. ...

Comments

Information & Contributors

Information

Published In

ACMSE '05 vol 1: Proceedings of the 43rd annual ACM Southeast Conference - Volume 1

March 2005

408 pages

ISBN:1595930590

DOI:10.1145/1167350

General Chair:
Mario Guimaraes
Kennesaw State University

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 ACM 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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 18 March 2005

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

ACM SE05

Sponsor:

ACM SE05: ACM Southeast Regional Conference 2005

March 18 - 20, 2005

Georgia, Kennesaw

Acceptance Rates

Overall Acceptance Rate 502 of 1,023 submissions, 49%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
154
Total Downloads

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

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Lin YMouratidis K(2015)Best upgrade plans for single and multiple source-destination pairsGeoinformatica10.1007/s10707-014-0219-119:2(365-404)Online publication date: 1-Apr-2015
https://dl.acm.org/doi/10.1007/s10707-014-0219-1
Lin YMouratidis K(2013)Best Upgrade Plans for Large Road NetworksProceedings of the 13th International Symposium on Advances in Spatial and Temporal Databases - Volume 809810.5555/2960717.2960734(223-240)Online publication date: 21-Aug-2013
https://dl.acm.org/doi/10.5555/2960717.2960734
Lin YMouratidis K(2013)Best Upgrade Plans for Large Road NetworksAdvances in Spatial and Temporal Databases10.1007/978-3-642-40235-7_13(223-240)Online publication date: 2013
https://doi.org/10.1007/978-3-642-40235-7_13
Badawy GSayegh ATodd T(2009)Managing traffic growth in solar powered wireless mesh networksProceedings of the 28th IEEE conference on Global telecommunications10.5555/1811982.1812049(4022-4027)Online publication date: 30-Nov-2009
https://dl.acm.org/doi/10.5555/1811982.1812049
Badawy GSayegh ATodd T(2009)Managing Traffic Growth in Solar Powered Wireless Mesh NetworksGLOBECOM 2009 - 2009 IEEE Global Telecommunications Conference10.1109/GLOCOM.2009.5425730(1-6)Online publication date: Nov-2009
https://doi.org/10.1109/GLOCOM.2009.5425730
Nepal KPark DChoi C(2009)Upgrading Arc Median Shortest Path Problem for an Urban Transportation NetworkJournal of Transportation Engineering10.1061/(ASCE)0733-947X(2009)135:10(783)135:10(783-790)Online publication date: Oct-2009
https://doi.org/10.1061/(ASCE)0733-947X(2009)135:10(783)

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.

PDF

eReader

View online with eReader.

eReader

Abstract

References

Cited By

Recommendations

Complexities of some interesting problems on spanning trees

Limits of minimum circuit size problem as oracle

On the (non) NP-hardness of computing circuit complexity

Comments

Information

Published In

Sponsors

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Conference

Acceptance Rates

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

Login options

Full Access

View options

PDF

eReader

Share

Share this Publication link

Share on social media

Affiliations