A Polynomial Algorithm for a Class of 0–1 Fractional Programming Problems Involving Composite Functions, with an Application to Additive Clustering

DOI10.1007/978-1-4939-0742-7_2zbMath1365.90248OpenAlexW1033702490MaRDI QIDQ5270613

Christophe Meyer, Pierre Hansen

Publication date: 26 June 2017

Published in: Clusters, Orders, and Trees: Methods and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-1-4939-0742-7_2

zbMATH Keywords

submodular functionpolynomial algorithmcomposite functionsadditive clustering0-1 fractional programming

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Abstract computational complexity for mathematical programming problems (90C60) Fractional programming (90C32)

Related Items

On the complexity and approximation of the maximum expected value all-or-nothing subset

Uses Software

• MAPCLUS
• Indclus

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A comparison of two methods for fitting the INDCLUS model
• Structural and algorithmic properties for parametric minimum cuts
• How much precision is needed to compare two sums of square roots of integers?
• A faster strongly polynomial time algorithm for submodular function minimization
• GENNCLUS: New models for general nonhierarchical clustering analysis
• Maximizing a supermodular pseudoboolean function: A polynomial algorithm for supermodular cubic functions
• On submodular function minimization
• MAPCLUS: A mathematical programming approach to fitting the ADCLUS model
• The ellipsoid method and its consequences in combinatorial optimization
• Hyperbolic 0-1 programming and query optimization in information retrieval
• Geometric algorithms and combinatorial optimization
• An alternating combinatorial optimization approach to fitting the INDCLUS and generalized INDCLUS models
• A modification of the SINDCLUS algorithm for finding the ADCLUS and INCLUS models
• On the supermodular knapsack problem
• A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
• Minimizing submodular functions over families of sets
• Approximating a class of combinatorial problems with rational objective function
• Maximizing Non-monotone Submodular Functions
• Maximizing the Product of Two Linear Functions In 0-1 Variables
• A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
• A sixth bibliography of fractional programming
• Complexity of some parametric integer and network programming problems
• A network flow solution to some nonlinear 0-1 programming problems, with applications to graph theory
• Mathematical Techniques for Efficient Record Segmentation in Large Shared Databases
• Minimizing a Submodular Function on a Lattice
• A Faster Scaling Algorithm for Minimizing Submodular Functions
• A Fast Parametric Maximum Flow Algorithm and Applications
• A bad network problem for the simplex method and other minimum cost flow algorithms
• Programming with linear fractional functionals
• Some Network Flow Problems Solved with Pseudo-Boolean Programming
• On Nonlinear Fractional Programming
• A Selection Problem of Shared Fixed Costs and Network Flows
• Notes—On a Selection Problem
• Fractional Programming
• On the polynomial mixed 0-1 fractional programming problems