frequency of assignment problem

DOI: 10.1109/PROC.1980.11899
Corpus ID: 37268885

Frequency assignment: Theory and applications

Published in Proceedings of the IEEE 1 December 1980
Mathematics, Computer Science

Figures from this paper

1,389 Citations

Graph-theoretical models for frequency assignment problems, solving frequency assignment problems via tree-decomposition 1, heuristics for frequency assignment problem with realistic interference constraints, dynamic multiple neighborhood structures for the static frequency assignment problem, lower bounding techniques for frequency assignment, a dynamic tabu search approach for solving the static frequency assignment problem, frequency assignment problem with net filter discrimination constraints, a decomposed approach for the minimum interference frequency assignment.

Highly Influenced

Feasible Cellular Frequency Assignment Using Constraint Programming Abstractions

T-colorings of multigraphs in frequency assignment, 69 references, a frequency assignment algorithm based on a minimum residual difficulty heuristic, chromatic scheduling and the chromatic number problem, the complexity of near-optimal graph coloring, graph coloring algorithms, on various algorithms for estimating the chromatic number of a graph, a new method to find out the chromatic partition of a symmetric graph, the solution of the graph-coloring problem as a set-covering problem, some simplified np-complete problems, a note on the complexity of the chromatic number problem, a heuristic technique for assigning frequencies to mobile radio nets, related papers.

Showing 1 through 3 of 0 Related Papers

Academia.edu no longer supports Internet Explorer.

To browse Academia.edu and the wider internet faster and more securely, please take a few seconds to upgrade your browser .

Enter the email address you signed up with and we'll email you a reset link.

We're Hiring!
Help Center

Frequency assignment problems

HANDBOOK OF COMBINATORIAL OPTIMIZATION D.-Z. Du and PM Pardalos (Eds.) pp. 295-377 (c) 1999 Kluwer Academic Publishers Frequency Assignment Problems Robert A. Murphey Wright Laboratory Eglin AFB, FL 32542 USA E-mail: murpheyQeglin. af. mil Panos M. Pardalos Center for Applied Optimization, ISE Department University of Florida, Gainesville, FL 32611 USA E-mail: pardalosOufl. edu Mauricio GC Resende Information Sciences Research Center AT&T Labs Research, Florham Park, NJ 07932 USA E-mail: mgcr9research. att.

Related Papers

Discussiones Mathematicae Graph Theory

Arie Koster

SIAM Journal on Discrete Mathematics

Justie Juan

Graphs and Combinatorics

Gerard Chang

Sergiy Butenko

This chapter aims to provide a detailed survey of existing graph models and algorithms for important problems that arise in different areas of wireless telecommunication. In particular, applications of graph optimization problems such as minimum dominating set, minimum vertex coloring and maximum clique in multihop wireless networks are discussed. Different forms of graph domination have been used extensively to model clustering in wireless ad hoc networks.

Discrete Mathematics

Sanming Zhou

iir publications

European Journal of Combinatorics

IEEE International Conference on Systems, Man and Cybernetics

Sanjay E. Sarma

Theoretical Computer Science

Computer Science > Networking and Internet Architecture

Title: frequency assignment problem with net filter discrimination constraints.

Abstract: Managing radio spectrum resources is a crucial issue. The frequency assignment problem (FAP) basically aims to allocate, in an efficient manner, limited number of frequencies to communication links. Geographically close links, however, cause interference, which complicates the assignment, imposing frequency separation constraints. The FAP is closely related to the graph-coloring problem and it is an NP-hard problem. In this paper, we propose to incorporate the randomization into greedy and fast heuristics. As far as being implemented, the proposed algorithms are very straight forward and are without system parameters that need tuned. The proposed algorithms significantly improve, quickly and effectively, the solutions obtained by greedy algorithms in terms of the number of assigned frequencies and the range. The enhanced versions of proposed algorithms perform close to the lower bounds while running for a reasonable duration. Another novelty of our study is its consideration of the net filter discrimination effects in the communication model. Performance analysis is done by synthetic and measured data, where the measurement data includes the effect of the real 3-dimensional (3D) geographical features in the Daejeon region in Korea. In both cases, we observe a significant improvement by employing randomized heuristics.

Subjects:	Networking and Internet Architecture (cs.NI)
Cite as:	[cs.NI]
	(or [cs.NI] for this version)
	Focus to learn more arXiv-issued DOI via DataCite

Submission history

Access paper:.

Other Formats

References & Citations

Google Scholar
Semantic Scholar

DBLP - CS Bibliography

Bibtex formatted citation.

Bibliographic and Citation Tools

Code, data and media associated with this article, recommenders and search tools.

Institution

arXivLabs: experimental projects with community collaborators

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs .

Frequency Assignment Problems

Cite this chapter.

Robert A. Murphey 4 ,
Panos M. Pardalos 5 &
Mauricio G. C. Resende 6

1472 Accesses

39 Citations

The term frequency assignment has been used to describe many types of problems which, quite often, have different modeling needs and objectives. These problems include:

Planning models for permanent spectrum allocation, licensing, and regulation which maximize utilization of all radio spectra [94].

Planning models for network design within a given allocation to include; aeronautical mobile, land mobile, maritime mobile, broadcast, land fixed (point-to-point) and satellite.

On-line algorithms for dynamically assigning frequencies to users within an established network. Of special interest here are land cellular mobile systems, where an enormous amount of research has been done. A paper by Katzela and Naghshineh [55] contains nearly 100 references to works just in cellular dynamic channel assignment.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Subscribe and save.

Get 10 units per month
Download Article/Chapter or eBook
1 Unit = 1 Article or 1 Chapter
Cancel anytime
Available as PDF
Read on any device
Instant download
Own it forever
Compact, lightweight edition
Dispatched in 3 to 5 business days
Free shipping worldwide - see info
Durable hardcover edition

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Unable to display preview. Download preview PDF.

Efficient Solution Methods for the Cumulative-Interference Channel Assignment Problem Using Integer Optimization and Constraint Programming

An exact algorithm for a resource allocation problem in mobile wireless communications.

Optimizing utilization in cellular radio networks using mobility data

K.I. Aardal, A. Hipolito, C.P.M. Van Hoesel, B. Jansen, C. Roos and T. Terlaky, A branch-and-cut algorithm for the frequency assignment problem, EUCLID CALMA Project ,Delft and Eindhoven Universities of Technology, The Netherlands, (1995)

Google Scholar

E. Aarts and J. Korst, Simulated Annealing and Boltzman Machines: A Stochastic Approach To Combinatorial Optimization and Neural Computing , John Wiley and Sons (1989) .

I. Baybars, Optimal assignment of broadcasting frequencies, European Journal of Operations Research , Vol. 9, (1982) pp. 257–263.

Article MATH Google Scholar

E. A. Bender and H. S. Wilf, A theoretical analysis of backtracking in the graph coloring problem, Journal of Algorithms 6 , (1985), pp. 275–282.

H.P. Benthem, GRAPH: Generating radio link frequency assignment problems heuristically, Master’s Thesis, Faculty of Technical Mathematics and Informatics, Delft University, Delft, The Netherlands, (1995).

H. van Benthem, A. Hipolito, B. Jansen, C. Roos, T. Terlaky and J. Warners, EUCLID CALMA technical report, GRAPH: a test case generator, generating radiolink frequency assignment problems heuristically, EUCLID CALMA Project , Delft and Eindhoven Universities of Technology, The Netherlands, (1995).

H. van Benthem, A. Hipolito, B. Jansen, C. Roos, T. Terlaky and J. Warners, GRAPH, a test problem generator for the radiolink frequency assignment problem, EUCLID CALMA Project Supplemental Report 2.3.2a :, Delft and Eindhoven Universities of Technology, The Netherlands, (1995).

L.A. Berry and D. H. Cronin, The spectrum cost of frequency distance rules, IEEE International Symposium on Electromagnetic Compatibility , (1983) pp. 75–78.

D.P. Bertsekas and R. G. Gallager, Data Networks , 2nd ed , (Prentice-Hall, 1992 ).

B. Bollobâs and A. J. Harris, List colorings of graphs, Graphs and Combinatoricsl, (1985) pp. 115–187

I. Bonias, T-colorings of complete graphs, Ph.D. Thesis, Department of Mathematics, Northeastern University, Boston, MA (1991).

A. Bouju, J.F. Boyce, C.H.D. Dimitropoulis, G. vom Scheidt, and J.G. Taylor, Tabu search for the radio link frequency assignment problem, Applied Decision Technologies , London [ADT951 , UNICOM Conference , (1995).

F. Box, A heuristic technique for assigning frequencies to mobile radio nets, IEEE Trans. Vehicular Technology , Vol. VT-27, (1978), pp. 57–74.

D. Brelaz, New methods to color the vertices of a graph, Communications ACM , Vol. 22 , (1979) pp. 251–256.

Article MathSciNet MATH Google Scholar

S.H. Cameron, The solution of the graph coloring problem as a set covering problem, IEEE Transactions on Electromagnetic Compatibility , Vol EMC-19, (1973) pp. 320–322.

F. Carmassi and L. Tornati, A theory of frequency assignment in broadcasting network planning, European Broadcast Union Technical Review , No. 198, (Apr. 1983) pp. 72–81.

D.J. Castelino, S. Hurley and N.M. Stephens, A Tabu search algorithm for frequency assignment, Annals of Operations Research , Vol 41, (1993), pp. 343–358.

Article Google Scholar

D. Castelino and N. Stephens, Tabu thresholding for the frequency assignment problem, Meta-Heuristics: Theory and Applications (Edited by I.H. Osman and J.P. Kelly ), Kluwer Academic Publishers 1996.

V. Chvâtal, Perfectly ordered graphs, Annals of Discrete Mathematics , 21 , (1984) pp. 63–65.

L.W. Couch, Modern Communications Systems: Principles and Practices , Prentice-Hall, Inc., (1995).

M.B. Cozzens and F.S. Roberts, T-colorings of graphs and the channel assignment problem, Congressus Numerantium ,Vol 35 (1982), pp. 191208.

M.B. Cozzens and F.S. Roberts, Double semiorders and double indifference graphs, SIAM Journal Algebraic Discrete Methods 3 (1982) pp. 566–583.

M.B. Cozzens and F.S. Roberts, Greedy algorithms for T-colorings of complete graphs and the meaningfulness of conclusions about them, Journal of Combinatorics , Information and System Sciences , Vol 16 No. 4, (1991), pp. 286–299.

MathSciNet MATH Google Scholar

M.B. Cozzens and D.I. Wang, The general channel assignment problem, Congressus Numerantium , Vol 41 (1984), pp. 115–129.

MathSciNet Google Scholar

W. Crompton, S. Hurley and N.M. Stephens, Frequency assignment using a parallel genetic algorithm, Proceedings of Natural Algorithms in Signal Processing , (1993).

C.E. Dadson, J. Durkin and R.E. Martin, Computer prediction of field strength in the planning of radio systems, IEEE Trans. Vehicular Technology , Vol. VT-24, (1975), pp. 1–8.

D. de Werra and Y. Gay, Chromatic scheduling and frequency assignment, Discrete Applied Mathematics 49 , (1994) pp. 165–174.

J. P. Doignon, Threshold representations of multiple semiorders, SIAM Journal Algebraic Discrete Methods 8 (1987) pp. 77–84.

R.B. Eggleton, P. Erdös and D.K. Skilton, Coloring the real line, Journal of Combinatorial Theory , Series B , 39 , (1985), 86–100.

Eindhoven RLFAP Group, Radio link frequency assignment project, EUCLID CALMA Project Report 2.3.3 Local Search :, Eindhoven University of Technology, The Netherlands, (1995).

A. Eisenblätter, A frequency assignment problem in cellular phone networks (extended abstract), Network Design , Connectivity and Facility Location , DIMACS Series in Discrete Mathematics and Theoretical Computer Science , Vol. 35, American Mathematical Society (1997).

P. Erdös, A. L. Rubin and H. Taylor, Choosability in graphs, Congres-sus Numerantium 26 , (1979), pp. 125–157.

L.R. Foulds, Graph Theory Application , Springer-Verlag New York Inc., (1992).

R.A. Frazier, Compatibility and the frequency selection problem, IEEE Trans. Electromagnetic Compatibility ,Vol. EMC-17, (1975), pp. 248275.

D. R. Fulkerson and O.A. Gross, Incidence matrices and interval graphs, Pacific Journal of Math 15 , (1965) pp. 835–855.

Z. Füredi, J. R. Griggs and D.J. Kleitinan, Pair labellings with given distance, SIAM Journal of Discrete Mathematics 2 , (1989) pp. 491–499.

A. Gamst, Some lower bounds for a class of frequency assignment problems, IEEE transactions on vehicular technology , Vol. VT -35, No. 1 (Feb. 1986), pp. 8–14.

A. Gamst and K. Ralf, Computational complexity of some interference graphs, IEEE Transactions on Vehicular Technology , Vol 39 No. 2, (1990) pp. 140–149.

A. Gamst and W. Rave, On frequency assignment in mobile automatic telephone systems, GLOBCOM 82 , IEEE Global Telecommunications Conference , Vol 1 , (1982) pp. 309–315.

M. R. Garey and D. S. Johnson, Computers and Intractability , A Guide To The Theory of NP-Completeness , W.H. Freeman and Company, New York, NY (1979).

F. Glover, Tabu search - Part I. ORSA Journal on Computing 1 : 190206, 1989.

F. Glover, Tabu search–Part II. ORSA Journal on Computing 2 : 4–32, 1990.

F. Glover, Tabu Thresholding: Improved search strategies by non-monotonic search trajectories, ORSA Journal on Computing to appear.

D.E. Goldberg, Genetic Algorithms in Search , Optimization and Machine Learning , Addison-Wesley, Reading MA (1989).

M. Grötschel, L. Lovâsz, and A. Schrijver, The ellipsoid method and its consequences in combinatorial optimization, Combinatorica 1 , (1981) 169–197.

W.K. Hale, Frequency assignment: theory and applications, Proc. of The IEEE Vol 68, No. 12, (1980) pp. 1497–1514.

W.K. Hale, New spectrum management tools, IEEE International Symposium on Electromagnetic Compatibility , Boulder, CO (1981) pp. 4753.

F. Harary, Graph Theory , Addison-Wesley Publishing Company, Reading, MA (1969).

A. Hertz, COSINE: a new graph coloring algorithm, Operations Research Letters 10 , (1991) pp. 411–415.

H. Holland, Adaptation in Natural and Artificial Systems , University of Michigan Press, Ann Arbor, MI (1975).

S. Hurley and D. H. Smith, Fixed spectrum frequency assignment using natural algorithms, Genetic Algorithms in Engineering Systems: Innovations and Applications , IEE Conference Publication No. 414, (1995).

T.R. Jensen and B. Toft, Graph Coloring Problems , John Wiley and Sons, New York, (1995).

MATH Google Scholar

P.K. Johri, An insight into dynamic channel assignment in cellular mobile communications systems, European Journal of Operations Research , 74 , (1994) pp. 70–77.

N. Karmarkar, An interior point approach to NP-Complete problems - part 1, Contemporary Mathematics , Vol 114, (1990) pp. 297–308.

I. Katzela and M. Naghshineh, Channel assignment schemes for cellular mobile telecommunication systems: a comprehensive survey, IEEE Personal Communications (June 1996), pp. 10–31.

D. Karger, R. Motwani and M. Sudan, Approximate graph coloring by semidefinite programming, INCOMPLETE

S. Kirkpatrick, C.D, Gelatt, Jr., and M.P. Vecchi, Optimization by simulated annealing, Science , Vol 220 , (1983) pp. 671–680.

Y. Kishi, T. Mizuike and F. Watanabe, A unified approach for frequency assignment of cellular mobile networks, Third Annual International Conference on Universal Personal Communications , San Diego , CA , (1994) pp. 563–567.

T. Kurokawa and S. Kozuka, Use of neural networks for the optimum frequency assignment problem, Electronics and Communications in Japan , Part 1, Vol, 77, No, 11, (1994).

T.A. Lanfear, Graph Theory and Radio Frequency Assignment , Tech nical Report, Allied Radio Frequency Agency NATO Headquarters, B1110, Brussels, Belgium, (1989).

D.S.P. Leung, Application of the partial backtracking technique to the frequency assignment problem, IEEE International Symposium on Electromagnetic Compatibility , Boulder, CO (1981) pp. 70–74.

D. D. Liu, Graph homomorphisms and the channel assignment problem, Ph.D. Thesis, Department of Mathematics, University of South Carolina, Colombia, SC (1991).

D.W. Matula and L.L. Beck, Smallest-last ordering and clustering and graph coloring algorithms, Journal of The ACM , Vol. 30, (1983) pp. 417–427.

B.H. Metzger, Spectrum management technique, paper presented at the 38th National ORSA Meeting , Detroit, MI, (1970).

L.C. Middlecamp, UHF taboos–history and development, IEEE Transactions on Consumer Electronics , Vol CE24, (1978) pp. 514–519.

G.L. Nemhauser and L.A. Wolsey, Integer and Combinatorial Optimization , John Wiley and Sons, Inc., (1988).

R.J. Opsut and F.S. Roberts, I-colorings, I-phasings, and I-intersection assignments for graphs, and their applications, Networks , Vol. 13 (1983) pp. 327–345.

P.M. Pardalos, F. Rendl and H. Wolkowicz, The Quadratic Assignment Problem: A Survey and Recent Developments, Quadratic Assignment and Related Problems , Panos M. Pardalos and Henry Wolkowicz (eds.) , DIMACS Series on Discrete Mathematics and Theoretical Computer Science , 16 American Mathematical Society, (1994) pp. 317–342.

J. Peemöller, A correction to Brelaz’s modification of Brown’s coloring algorithm, Communications of the ACM , Vol. 26, No. 8 , (1983) pp. 595–597.

A. Quellmalz, A. Knälmann and B. Müller, Efficient frequency assignment with simulated annealing, IEE Ninth International Conference on Antennas and Propagation , Eindhoven, The Netherlands, Vol. 2 , (1995).

A. Raychaudhuri, Intersection assignments, T-coloring, and powers of graphs, Ph.D . Thesis, Department of Mathematics, Rutgers University, New Brunswick, NJ, (1985).

A. Raychaudhuri, Further results on T-coloring and frequency assignment problems, SIAM Journal on Discrete Mathematics , Vol. 7 (1994), pp. 605–613.

F.S. Roberts, On the Compatibility between a graph and a simple order, Journal Combinatorial Theory , 11 (1971), pp 28–38.

F.S. Roberts, On the mobile radio frequency assignment problem and the traffic light phasing problem, Annals of New York Academy of Sciences Vol . 319 (1979) pp 466–483.

F.S. Roberts, From garbage to rainbows: generalizations of graph coloring and their applications, in Y. Alavi, G. Chartrand, O.R. Oellerman and A.J. Schwenk (eds.) Graph Theory , Combinatorics , and Applications , Vol . 2 ( Wiley, New York, 1991 ), pp. 1031–1052.

F.S. Roberts, T-colorings of graphs: recent results and open problems, Discrete Math . 93 , (1991) pp. 229–245.

F.S. Roberts, No-hole 2-distant colorings, Mathl. Comput. Modelling Vol. 17, No. 11 (1993) pp. 139–144.

D. Sakai, Generalized graph colorings and unit interval graphs, Ph.D. Thesis, RUTCOR, Rutgers University, New Brunswick University, NJ (1992).

D. Sakai and C. Wang, No-hole (r+1)-distant colorings, Discrete Math . 119 , (1993), pp. 175–189.

S. S. Skiena, The Algorithm Design Manual , TELOS, Springer-Verlag New York Inc., (1998).

D.H. Smith, Graph coloring and frequency assignment, ARS Combinatorica , Vol . 25C, (1988) pp. 205–212.

G.D. Smith, A. Kapsalis, V.J. Rayward-Smith, Radio link frequency assignment project, EUCLID CALMA Project Report 2.1 Genetic Algorithm Approaches to Solving the Radio Link Frequency Assignment Problem :, University of East Anglia, UK (1995).

S. Stahl, n-tuple colorings and associated graphs, J. Combinatorial Theory 20 (1976) pp. 185–203.

B.A. Tesman, T-colorings, list T-colorings, and set T-colorings of graphs, Ph.D. Thesis, Department of Mathematics, Rutgers University, New Brunswick, NJ, (1989).

B.A. Tesman, Applications of forbidden difference graphs to T- colorings, Congrussus Numerantium 74 (1990) pp. 15–24.

B. A. Tesman, Set T-colorings, Congrussus Numerantium 77 (1990) pp. 229–242.

S. Tiourine, C. Hurkins and J. K. Lenstra, An overview of algorithmic approaches to frequency assignment problems, EUCLID CALMA Project Overview Report , Delft University of Technology, The Netherlands, (1995).

D. Sakai Troxell, No-hole k-tuple (r+1)-distant colorings, Discrete Applied Math . 64 , (1996) pp. 67–85.

D. -I . Wang, The channel assignment problem and closed neighborhood containment graphs, Ph.D. Thesis, Northeastern University, Boston, MA (1985).

J.P. Warners, T. Terlaky, C. Roos and B. Jansen, A Potential Reduction Approach to The Frequency Assignment Problem , Technical Report 9598, Faculty of Technical Mathematics and Informatics, Delft University, Delft, The Netherlands, (1995).

D. Werra, Y. Gay, Chromatic scheduling and frequency assignment, Discrete Applied Math . 49 , (1994) pp. 165–174.

H.S. Wilf, Backtrack: an 0(1) expected time algorithm for the graph coloring problem, Information Processing Letters 18 (1984) pp. 119121.

A. Wisse, Mathematical model for the radio link frequency assignment problem, EUCLID CALMA Project , Delft University of Technology, The Netherlands, (1994).

J.A. Zoellner, Frequency assignment games and strategies, IEEE Transactions on Electromagnetic Compatibility ,Vol EMC-15, (1973) pp. 191196.

J.A. Zoellner and C.L. Beall, A breakthrough in spectrum conserving frequency assignment technology, IEEE Transactions on Electromagnetic Compatibility , Vol EMC-19, (1977) pp. 313–319.

Download references

Author information

Authors and affiliations.

Wright Laboratory, Eglin AFB, FL, 32542, USA

Robert A. Murphey

Center for Applied Optimization, ISE Department, University of Florida, Gainesville, FL, 32611, USA

Panos M. Pardalos

Information Sciences Research Center, AT&T Labs Research, Florham Park, NJ, 07932, USA

Mauricio G. C. Resende

You can also search for this author in PubMed Google Scholar

Editor information

Editors and affiliations.

Department of Computer Science, University of Minnesota, USA

Ding-Zhu Du

Institute of Applied Mathematics, Academia Sinica, P. R. China

Department of Industrial and Systems Engineering, University of Florida, USA

Rights and permissions

Reprints and permissions

Copyright information

About this chapter

Murphey, R.A., Pardalos, P.M., Resende, M.G.C. (1999). Frequency Assignment Problems. In: Du, DZ., Pardalos, P.M. (eds) Handbook of Combinatorial Optimization. Springer, Boston, MA. https://doi.org/10.1007/978-1-4757-3023-4_6

Download citation

DOI : https://doi.org/10.1007/978-1-4757-3023-4_6

Publisher Name : Springer, Boston, MA

Print ISBN : 978-1-4419-4813-7

Online ISBN : 978-1-4757-3023-4

eBook Packages : Springer Book Archive

Share this chapter

Anyone you share the following link with will be able to read this content:

Sorry, a shareable link is not currently available for this article.

Provided by the Springer Nature SharedIt content-sharing initiative

Publish with us

Policies and ethics

Find a journal
Track your research

IEEE Account

Change Username/Password
Update Address

Purchase Details

Payment Options
Order History
View Purchased Documents

Profile Information

Communications Preferences
Profession and Education
Technical Interests
US & Canada: +1 800 678 4333
Worldwide: +1 732 981 0060
Contact & Support
About IEEE Xplore
Accessibility
Terms of Use
Nondiscrimination Policy
Privacy & Opting Out of Cookies

A not-for-profit organization, IEEE is the world's largest technical professional organization dedicated to advancing technology for the benefit of humanity. © Copyright 2024 IEEE - All rights reserved. Use of this web site signifies your agreement to the terms and conditions.

IMAGES

Example of frequency assignment problem.
Example of frequency assignment problem.
A frequency assignment for the example problem
Frequency assignment span for the problems 5 (a), 6 (b) and 7 (c
(PDF) Frequency assignment problem using discrete particle swarm model
(PDF) Models and Applications of Frequency Assignment Problem

VIDEO

Assignment problem
Week 3
Assignment Problem ( Brute force method) Design and Analysis of Algorithm
Frequency assignment Meaning
Balanced assignment problem in Operations Research
High frequency word list: Second Grade

COMMENTS

Frequency Assignment Problem
This formulation, where adjacent vertices cannot share the same frequency is termed co-channel constrained and was shown by B.H. Metzger [] to be equivalent to the well-studied graph coloring problem.Typically, the objective is to find an assignment of frequencies (colors) to the transmitters (vertices) that minimizes the number of frequencies (colors) used.
PDF The Frequency Assignment Problem
The Frequency Assignment Problem Angela Erika Koller Submitted for the degree of Doctor of Philosophy 2004 Abstract This thesis examines a wide collection of frequency assignment problems. One of the largest topics in this thesis is that of L(2,1)-labellings of outerplanar graphs.
PDF Models and solution techniques for frequency assignment problems
broadcasting, and most recently wireless LANs contributed to the literature on frequency assignment in recent years. This paper is not the ﬁrst survey on the frequency assignment problem. Already Hale (1980) presented an overview of the frequency planning problems of that time, with a spe-cial focus on modeling the problems.
Frequency assignment: Theory and applications
The frequency constrained approach should be avoided if distance separation is employed to mitigate interference. A restricted class of graphs, called disk graphs, plays a central role in frequency-distance constrained problems. We introduce two generalizations of chromatic number and show that many frequency assignment problems are equivalent ...
Frequency assignment: Theory and applications
Frequency assignment: Theory and applications. W. K. Hale. Published in Proceedings of the IEEE 1 December 1980. Mathematics, Computer Science. TLDR. This paper introduces the minimum-order approach to frequency assignment and presents a theory which relates this approach to the traditional one, and shows that many frequency assignment problems ...
Solving the frequency assignment problem by using meta-heuristic
Frequency assignment, as a subclass of general assignment problem, is a non-deterministic polynomial-time hard (NP-hard) optimization problem. Main difficulty in these types of problems is the time required to find an optimum solution, since the solution time increases exponentially as the size of the problem grows. To solve the problem in a limited computation time, meta-heuristic methods are ...
The dynamic frequency assignment problem
In this paper, we consider a frequency assignment problem occurring in a military context. This problem was submitted by the CELAR (Centre ELectronique de L'ARmement) and concerns the assignment of frequencies to Hertzian communications in the course of a military deployment. The main originality of the problem pertains to its dynamic dimension.
Frequency Assignment Problem
Frequency assignment problems are typically modeled in graph theoretical terms. That is, a graph G(V, E) is considered with vertices V (G) = {v 1, …, v n} and edges E(G).Each vertex in V(G) represents a transmitter and two vertices (v i, v j) are adjacent (have an edge between them) if the corresponding transmitters are not permitted to share the same frequency.
Models and Applications of Frequency Assignment Problem
The Frequency Assignment Problem (FAP) in radio networks is the problem of assigning frequencies to transmitters exploiting frequency reuse while keeping signal interference to acceptable levels ...
Frequency Assignment Problem
4 Frequency Assignment Problem size problems [1]. A potential reduction method [18] has also been developed that utilizes the transformation xif = 2xif − 1, that is, xif ∈ {−1,+1}. As a result, any feasible solution to the transformed IPs must satisfy x x = mn where x is a vector of xif in Zmn+. The polyhedron P formed from the linear ...
PDF Solving Frequency Assignment Problems with Constraint Programming
The problem of assigning channels to TRXs while taking additional require-ments into account is called the Frequency Assignment Problem (FAP). Our optimization goal is to minimize the sum of all co- and adjacent channel inter-ferences, but other objectives are possible. In the early nineties, frequency planning in GSM networks was often performed
Bounds for the frequency assignment problem
The problem of assigning radio frequencies to a set of transmitters in a region is related to the theory of vertex colourings of graphs. Real frequency assignment problems often deal with a large number of transmitters. Exact methods of solution may be impracticable and heuristic methods must be used. Lower bounds for the frequency assignment ...
(PDF) Frequency Assignment Problems
The term frequency assignment has been used to describe many types of problems which, quite often, have different modeling needs and objectives. These problems include: 1. Planning models for ...
(PDF) Frequency assignment problems
This chapter aims to provide a detailed survey of existing graph models and algorithms for important problems that arise in different areas of wireless telecommunication. In particular, applications of graph optimization problems such as minimum dominating set, minimum vertex coloring and maximum clique in multihop wireless networks are discussed.
[1605.04379] Frequency Assignment Problem with Net Filter
The frequency assignment problem (FAP) basically aims to allocate, in an efficient manner, limited number of frequencies to communication links. Geographically close links, however, cause interference, which complicates the assignment, imposing frequency separation constraints. The FAP is closely related to the graph-coloring problem and it is ...
PDF Frequency Assignment Problems
A frequency assignment problem (FAP) models the task of assigning radio spectrum to a set of transmitters. That is, if V is the set of all transmitters with v E V, f(v) denotes the continuum of frequencies assigned to v by the assignment rule f.
Frequency reassignment problem in mobile communication networks
However, there exist numerous studies on frequency assignment problem (FAP). Below, some of the distinguished research results on the FAP are summarized. One of the generic FAPs is to minimize the total number of frequencies, while satisfying the minimum distance requirements for all pairs of adjacent BSs. This type of FAP was dealt by Hale [3 ...
PDF FREQUENCY ASSIGNMENT PROBLEMS
FREQUENCY ASSIGNMENT PROBLEMS ROBERT A. MURPHEY, PANOS M. PARDALOS, AND MAURICIO G.C. RESENDE ... around the globe have made the optimal assignment of a limited radio frequency spectrum a problem ...
Frequency Assignment Problems
The term frequency assignment has been used to describe many types of problems which, quite often, have different modeling needs and objectives. These problems include: 1. Planning models for permanent spectrum allocation, licensing, and regulation which maximize utilization of all radio spectra [94]. 2.
Optimization of frequency assignment
A systematic method of determining carrier frequency assignment is proposed to minimize the cochannel interference in satellite communication systems. For the mathematical treatment of the problem, discrete positioning of carriers is introduced to avoid the nonlinear expression inherent in interference evaluation. The proposed method converts this nonlinear problem into the well-known ...