Combinatorial Optimization with Rational Objective Functions
From MaRDI portal
Publication:3861175
DOI10.1287/moor.4.4.414zbMath0425.90076OpenAlexW2027029507MaRDI QIDQ3861175
Publication date: 1979
Published in: Mathematics of Operations Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1287/moor.4.4.414
computational complexitycombinatorial optimizationnetwork algorithmspolynomial time algorithmsrational objective functionsminimum ratio spanning trees
Related Items
Faster Algorithms for Next Breakpoint and Max Value for Parametric Global Minimum Cuts, Node-Balancing by Edge-Increments, Using sparsification for parametric minimum spanning tree problems, Space-sweep algorithms for parametric optimization, Parametric problems on graphs of bounded tree-width, Optimal parametric search on graphs of bounded tree-width, Reputation games for undirected graphs, Approximating a class of combinatorial problems with rational objective function, Algorithms for the Densest Subgraph with at Least k Vertices and with a Specified Subset, Identification and validation of quasispecies models for biological systems, A global optimization algorithm for solving the minimum multiple ratio spanning tree problem, Continuous dynamic contraflow approach for evacuation planning, Optimal choice of machine speeds for two-stage non-homogeneous systems, A general approximation method for bicriteria minimization problems, Integrality in the multinetwork min‐cost equal‐flow problem, The quickest flow problem, The multi-weighted spanning tree problem, Budgeted Matching and Budgeted Matroid Intersection Via the Gasoline Puzzle, Max-max, max-min, min-max and min-min knapsack problems with a parametric constraint, Minmax centered \(k\)-partitioning of trees and applications to sink evacuation with dynamic confluent flows, Generalized Bottleneck Problems∗, A strongly polynomial algorithm for line search in submodular polyhedra, Faster distance-based representative skyline and \(k\)-center along Pareto front in the plane, On equilibria for ADM minimization games, Single machine scheduling with controllable release and processing parameters, Cyclic flowshop scheduling with operators and robots: Vyacheslav Tanaev's vision and lasting contributions, An Introduction to Network Flows over Time, Interdicting Structured Combinatorial Optimization Problems with {0, 1}-Objectives, Tow algorithms for finding a minimal ratio hamiltonian cycle in a network, Unnamed Item, Pricing and Assortment Strategies with Product Exchanges, Fast Algorithms for Diameter-Optimally Augmenting Paths and Trees, Fractional programming, AnO (n)-algorithm for LP-knapsacks with a fixed number of GUB constraints, Bottleneck Capacity Expansion Problems with General Budget Constraints, A class of inverse dominant problems under weighted \(l_{\infty }\) norm and an improved complexity bound for Radzik's algorithm, The constrained minimum weighted sum of job completion times problem, A survey on models and algorithms for discrete evacuation planning network problems, A new contraction technique with applications to congruency-constrained cuts, Greedy-Like Algorithms for Dynamic Assortment Planning Under Multinomial Logit Preferences, A Strongly Polynomial Algorithm for a Class of Minimum-Cost Flow Problems with Separable Convex Objectives, Differentially Private and Budget-Limited Bandit Learning over Matroids, Dynamic Assortment Personalization in High Dimensions, Traffic Networks and Flows over Time, The Stable Fixtures Problem with Payments, Approximation algorithms for combinatorial fractional programming problems, Linear-time algorithms for parametric minimum spanning tree problems on planar graphs, A Mixed-Integer Fractional Optimization Approach to Best Subset Selection, Polynomial-Time Approximation Schemes for Maximizing Gross Substitutes Utility Under Budget Constraints, One-way and round-trip center location problems, Finding Least-Distances Lines, A comprehensive simplex-like algorithm for network optimization and perturbation analysis, Optimization problems with algebraic solutions: Quadratic fractional programs and ratio games, Computing optimal scalings by parametric network algorithms, Bibliography in fractional programming, The shortest path problem with two objective functions, Computing maximum mean cuts, On the complexity and approximability of budget-constrained minimum cost flows, Linear and combinatorial sharing problems, Solving utility-maximization selection problems with multinomial logit demand: is the first-choice model a good approximation?, Budget-constrained minimum cost flows, Efficient contraflow algorithms for quickest evacuation planning, Parametric optimization of sequence alignment, An efficient, strongly polynomial, \(\varepsilon\)-approximation parametric optimization scheme, A PTAS for capacitated sum-of-ratios optimization, Efficient algorithms for center problems in cactus networks, The most critical path in a PERT network: A heuristic approach, One machine scheduling problem with fuzzy duedates, The economic lot-sizing problem with an emission capacity constraint, Multicommodity flows over time: Efficient algorithms and complexity, Approximating points by a piecewise linear function, Improved algorithms for some competitive location centroid problems on paths, trees and graphs, Real time scheduling with a budget: parametric-search is better than binary search, Strongly polynomial and fully combinatorial algorithms for bisubmodular function minimization, The cost-to-time ratio problem for large or infinite graphs, Minimum cost-reliability ratio path problem, The general facility location problem with connectivity on trees, Hybrid column generation for large-size covering integer programs: application to transportation planning, The stable fixtures problem with payments, On some large-scale LP relaxations for the graph partitioning problem and their optimal solutions, Optimal and approximate bottleneck Steiner trees, Partial multicuts in trees, Fractional 0-1 programming and submodularity, L-infinity interdistance selection by parametric search, Parametric search made practical, \(\varepsilon\)-approximation minimization of convex functions in fixed dimension, Revisiting \(k\)-sum optimization, Fractional 0-1 programming: applications and algorithms, Ratio combinatorial programs, Operations research applications of dichotomous search, The inverse-parametric knapsack problem, Linear-time algorithms for parametric minimum spanning tree problems on planar graphs, Risk models for the prize collecting Steiner tree problems with interval data, Decomposable multi-parameter matroid optimization problems., Optimizing healthcare network design under reference pricing and parameter uncertainty, Fuzzy random bottleneck spanning tree problems using possibility and necessity measures, Weight reduction problems with certain bottleneck objectives., On the solution of discrete bottleneck problems, Min max min robust (relative) regret combinatorial optimization, Approximation algorithm for minimizing total latency in machine scheduling with deliveries, An inverse model for the most uniform problem, On search over rationals, Optimal paths in bi-attribute networks with fractional cost functions, Improved complexity bounds for location problems on the real line, A fully polynomial time approximation scheme for minimum cost-reliability ratio problems, Scheduling on a hypercube, A branch-and-cut algorithm for the latent-class logit assortment problem, Solving a class of feature selection problems via fractional 0--1 programming, Negative circuits for flows and submodular flows, Revisiting Karnik-Mendel algorithms in the framework of linear fractional programming, A combinatorial interior point method for network flow problems, A generalized approximation framework for fractional network flow and packing problems, Computing the throughput of concatenation state machines, Two scheduling problems with fuzzy due-dates, On the tightness of an LP relaxation for rational optimization and its applications, Complexity analysis for maximum flow problems with arc reversals, Budgeted matching and budgeted matroid intersection via the gasoline puzzle, Improved algorithms for the continuous tree edge-partition problems and a note on ratio and sorted matrices searches, Strongly polynomial-time approximation for a class of bicriteria problems., Minimizing maximum risk for fair network connection with interval data, Efficient algorithms and implementations for optimizing the sum of linear fractional functions, with applications, Quadratic programming and combinatorial minimum weight product problems, An algorithm for source location in directed graphs, Optimization with additional variables and constraints, C-programming and the minimization of pseudolinear and additive concave functions, Conical partition algorithm for maximizing the sum of dc ratios, A linear-time algorithm for solving continuous maximin knapsack problems, Duality for balanced submodular flows, Submodular function minimization, Minsum \(k\)-sink problem on path networks, A strongly polynomial simplex method for the linear fractional assignment problem, Min-max controllable risk problems, The densest subgraph problem with a convex/concave size function, Center location problems on tree graphs with subtree-shaped customers, The subdivision-constrained minimum spanning tree problem, An FPTAS for the knapsack problem with parametric weights, Optimal building evacuation time considering evacuation routes, Approximation algorithms for maximum latency and partial cycle cover, Extending NC and RNC algorithms, Computing and minimizing the relative regret in combinatorial optimization with interval data, Computing the least quartile difference estimator in the plane, Two machine mixed shop scheduling problem with controllable machine speeds, A parametric characterization and an \(\epsilon\)-approximation scheme for the minimization of a quasiconcave program, Continuous bottleneck tree partitioning problems, Discrete Newton methods for the evacuation problem, An algorithm for fractional assignment problems, Minmax regret solutions for minimax optimization problems with uncertainty, Calculation of stability radii for combinatorial optimization problems, Locating service centers with precedence constraints, New polynomially solvable classes and a new heuristic for the traveling salesman problem and its generalization, The single most vital arc in the most economical path problem -- a parametric analysis, An algorithm for finding a matroid basis which maximizes the product of the weights of the elements, A scheme for exact separation of extended cover inequalities and application to multidimensional knapsack problems, Approximation algorithms for fractional knapsack problems, The maximum ratio clique problem
