Article

Free access

Optimizing the sum of linear fractional functions and applications

Authors:

Jinhui XuAuthors Info & Claims

SODA '00: Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms

Pages 707 - 716

Published: 01 February 2000 Publication History

PDF eReader

References

[1]

E. M. Arkin, Y.-J. Chiang, M. Held, J. S. B. Mitchell, V. Sacxistan, S. S. Skiena, and T.-C. Yang, On Minimum-Area Hulls, Algorithmica, 21:119-136, 1998.

Google Scholar

[2]

D. A. Bini and G. Fiorentino, Numerical Computation of Polynomial Roots: MPSolve-Version 2.0, in FRISCO Report, 1998.

Google Scholar

[3]

T. M. Chan, Deterministic Algorithms for ~-d Convex Programming and 3-d Online Linear Programming, Journal of Algorithms, 27:147-166, 1998.

Digital Library

Google Scholar

[4]

B. Chazelle, On the Convex Layers of a Planar Set, IEEE Transactions on Information Theory, 31(4):509- 517, 1985.

Google Scholar

[5]

D.Z. Chen, O. Daescu, X. Hu, X. Wu, and J. Xu, Determining an Optimal Penetration among Weighted Regions in Two and Three Dimensions, in Proc. of the 15th Annual ACM Symposium on Computational Geometry, pp. 322-331, 1999.

Digital Library

Google Scholar

[6]

D.Z. Chen and J. Xu, Peeling an arrangement topologically, manuscript, 1999.

Google Scholar

[7]

L. Craig, J.L. Zhou, and A.L. Tits, User's Guide for CFSQP Version ~.5, Electrical Eng. Dept: and Institute for Systems Research, University of Maryland, TR-94-16rl, 1994.

Google Scholar

[8]

K. Daniels, The Restrict/Evaluate/Subdivide Paradigm for Translational Containment, in Proc. Fifth MSI Stony Brook Workshop on Computational Geometry, 1995.

Google Scholar

[9]

H. Edelsbrunner, Algorithms in Combinatorial Geometry, Springer-Verlag, New York, 1987.

Digital Library

Google Scholar

[10]

D. Eppstein, Dynamic Three-Dimensional Linear Programming, in Proc. 32nd Annual IEEE Symposium on Foundations of Computer Science, pp. 488-494, 1991.

Digital Library

Google Scholar

[11]

J. E. Falk and S. W. Palocsay, Optimizing the Sum of Linear Fractional Functions, Collection: Recent Advances in Global Optimization, C.A. Floudas and P. M. Pardalos (eds.), pp. 221-258, 1992.

Digital Library

Google Scholar

[12]

S. Hashizume, M. Fukushima, N. Katoh, and T. ibaraki, Approximation Scheme for Combinatorial Fractional Programming Problems, Mathematical Programming, 37:255-267, 1987.

Digital Library

Google Scholar

[13]

L. Ingber, Adaptive Simulated Annealing, Optimization Algorithm for Nonlinear and Stochastic Systems, http://www.ingber.com/#ASA-CODE.

Google Scholar

[14]

M.Jelasity and J. Dombi, GAS Genetic Algorithm, ftp: / / ftp.j ate. uszeged.hu/pub/math/optimization/GAS/.

Google Scholar

[15]

H. Konno, T. Kuno, and Y. Yajima, Global Minimization of a Generalized Convex Multiplicative Function, Journal of Global Optimization, 4:47-62, 1994.

Google Scholar

[16]

G. Liotta, F. P. Preparata, and R. Tamassia, Robust Proximity Queries: An Illustration of Degree- Driven Algorithm Design, SIAM Journal on Computing, 28:864-889, 1998.

Digital Library

Google Scholar

[17]

J. Majhi, R. Janardan, J. Schwerdt, M. Staid, and P. Gupta, Minimizing Support Structures and Trapped Area in Two-Dimensional Layered Manufacturing, Technical Report TR-97-058, Dept. of Computer Science, University of Minnesota, Dec. 1997.

Google Scholar

[18]

J. Majhi, R. Janardan, M. Staid, and P. Gupta, On Some Geometric Optimization Problems in Layered Manufacturing, in Proc. 5th Workshop on Algorithms and Data Structures, pp. 136-149, Springer-Verlag, 1997.

Digital Library

Google Scholar

[19]

N. Megiddo, Linear Programming in Linear Time When the Dimension Is Fixed, Journal of ACM, 31:114- 127, 1984.

Digital Library

Google Scholar

[20]

Z. Michalewicz, GENOCOP III Genetic Algorithm for Constrained Problems, http://www.coe.uncc.edu/,~zbyszek/gcreadme.html.

Google Scholar

[21]

V. Milenkovic, K. Daniels, and Z. Li, Placement and Compaction of Nonconvex Polygons for Clothing Manufacture, in Proc. 4th Canad. Conf. Comput. Geom., pp. 236-243, 1992.

Google Scholar

[22]

F. P. Prepaxata and M. I. Shamos, Computational Geometry: An Introduction, Springer-Verlag, New York, 1985.

Digital Library

Google Scholar

[23]

T. Radzik, Newton's Method for Fractional Combinatorial Optimization, in Proc. 33rd Annual IEEE Symposium on Foundations of Computer Science, pp. 659-669, 1992.

Google Scholar

[24]

S. Schaible, Fractional Programming, Handbook of Global Optimization, R. Horst and P. M. Pardalos (eds.), Kluwer Academic Publishers, pp. 495-608, 1995.

Google Scholar

[25]

H. Yamashita, E~cient Algorithms for Minimizing the Sum and the Product of Linear Fractional Functions, Master Thesis, Dept. of Industrial Engineering and Management, Tokyo Institute of Technology, 1997.

Google Scholar

Cited By

View all

Benson H(2004)On the Global Optimization of Sums of Linear Fractional Functions over a Convex SetJournal of Optimization Theory and Applications10.1023/B:JOTA.0000026129.07165.5a121:1(19-39)Online publication date: 1-Apr-2004
https://dl.acm.org/doi/10.1023/B%3AJOTA.0000026129.07165.5a
Benson H(2003)Generating Sum-of-Ratios Test Problems in Global OptimizationJournal of Optimization Theory and Applications10.1023/B:JOTA.0000006959.01650.59119:3(615-621)Online publication date: 1-Dec-2003
https://dl.acm.org/doi/10.1023/B%3AJOTA.0000006959.01650.59
Kuno T(2002)A branch-and-bound algorithm for maximizing the sum of several linear ratiosJournal of Global Optimization10.1023/A:101380712984422:1-4(155-174)Online publication date: 1-Jan-2002
https://dl.acm.org/doi/10.1023/A%3A1013807129844

Index Terms

Optimizing the sum of linear fractional functions and applications
1. Mathematics of computing
  1. Discrete mathematics
  2. Mathematical analysis
    1. Mathematical optimization
      1. Continuous optimization
        Linear programming
2. Theory of computation
  1. Design and analysis of algorithms
    1. Mathematical optimization
      1. Continuous optimization
        Linear programming
  2. Randomness, geometry and discrete structures

Recommendations

Robust Finite-Time Stability of Fractional Order Linear Time-Varying Impulsive Systems

This paper considers the robust finite-time stability (FTS) of fractional order linear time-varying impulsive systems. First, using the fractional order Lyapunov function and generalized Gronwall inequality, some sufficient conditions are given to ...
Fractional-order Bernoulli functions and their applications in solving fractional FredholemVolterra integro-differential equations

In this paper, we define a new set of functions called fractional-order Bernoulli functions (FBFs) to obtain the numerical solution of linear and nonlinear fractional integro-differential equations. The properties of these functions are employed to ...
Fractional green function for linear time-fractional inhomogeneous partial differential equations in fluid mechanics

This paper deals with the solutions of linear inhomogeneous time-fractional partial differential equations in applied mathematics and fluid mechanics. The fractional derivatives are described in the Caputo sense. The fractional Green function method is ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SODA '00: Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms

February 2000

965 pages

ISBN:0898714532

Chairman:
David Shmoys

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 01 February 2000

Check for updates

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
777
Total Downloads

Downloads (Last 12 months)54
Downloads (Last 6 weeks)8

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Benson H(2004)On the Global Optimization of Sums of Linear Fractional Functions over a Convex SetJournal of Optimization Theory and Applications10.1023/B:JOTA.0000026129.07165.5a121:1(19-39)Online publication date: 1-Apr-2004
https://dl.acm.org/doi/10.1023/B%3AJOTA.0000026129.07165.5a
Benson H(2003)Generating Sum-of-Ratios Test Problems in Global OptimizationJournal of Optimization Theory and Applications10.1023/B:JOTA.0000006959.01650.59119:3(615-621)Online publication date: 1-Dec-2003
https://dl.acm.org/doi/10.1023/B%3AJOTA.0000006959.01650.59
Kuno T(2002)A branch-and-bound algorithm for maximizing the sum of several linear ratiosJournal of Global Optimization10.1023/A:101380712984422:1-4(155-174)Online publication date: 1-Jan-2002
https://dl.acm.org/doi/10.1023/A%3A1013807129844

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

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

Cited By

Index Terms

Recommendations

Robust Finite-Time Stability of Fractional Order Linear Time-Varying Impulsive Systems

Fractional-order Bernoulli functions and their applications in solving fractional FredholemVolterra integro-differential equations

Fractional green function for linear time-fractional inhomogeneous partial differential equations in fluid mechanics