scientific article; zbMATH DE number 1219584

Kenneth Steiglitz, Christos H. Papadimitriou

Publication date: 4 November 1998

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

optimization branch-and-bound algorithm approximation algorithm NP-completeness spanning tree flow integer linear programming primal-dual algorithm

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Abstract computational complexity for mathematical programming problems (90C60) Optimality conditions and duality in mathematical programming (90C46) Linear programming (90C05) Approximation methods and heuristics in mathematical programming (90C59) Deterministic network models in operations research (90B10) Combinatorial optimization (90C27) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to operations research and mathematical programming (90-01)

Related Items (only showing first 100 items - show all)

OPTIMIZING DATA THROUGHPUT IN CLIENT/SERVER SYSTEMS BY KEEPING QUEUE SIZES BALANCED ⋮ Solving Linear Programming with Constraints Unknown ⋮ Common due date assignment scheduling for a no-wait flowshop with convex resource allocation and learning effect ⋮ Navigating Weighted Regions with Scattered Skinny Tetrahedra ⋮ Min‐Max quickest path problems ⋮ Unnamed Item ⋮ Activity propagation in systems of linear inequalities and its relation to block-coordinate descent in linear programs ⋮ Soft robust solutions to possibilistic optimization problems ⋮ A local algorithm and its percolation analysis of bipartite z-matching problem ⋮ Distributionally robust possibilistic optimization problems ⋮ Walrasian equilibria from an optimization perspective: A guide to the literature ⋮ Optimally integrating ad auction into e-commerce platforms ⋮ A neural network approach to performance analysis of tandem lines: the value of analytical knowledge ⋮ A 3/4 differential approximation algorithm for traveling salesman problem ⋮ Granular approximations: a novel statistical learning approach for handling data inconsistency with respect to a fuzzy relation ⋮ Using predictability to improve matching of urban locations in Philadelphia ⋮ A Message-Passing Approach to Phase Retrieval of Sparse Signals ⋮ Exact and heuristic solutions for the prize‐collecting geometric enclosure problem ⋮ The Greedy Algorithm and the Cohen-Macaulay Property of Rings, Graphs and Toric Projective Curves ⋮ Randomized Algorithms for Lexicographic Inference ⋮ A new metric between distributions of point processes ⋮ A Light Modality for Recursion ⋮ Graph Clustering Via Intra-Cluster Density Maximization ⋮ A general system for heuristic minimization of convex functions over non-convex sets ⋮ A Worst-Case Analysis of Constraint-Based Algorithms for Exact Multi-objective Combinatorial Optimization ⋮ Quantitative Logic Reasoning ⋮ An introduction to quantum annealing ⋮ Unnamed Item ⋮ The heuristic approach in finding initial values for minimum density power divergence estimators ⋮ On Data Recovery in Distributed Databases ⋮ On the Nearest-Neighbor Algorithm for the Mean-Field Traveling Salesman Problem ⋮ The Secret Life of Keys: On the Calculation of Mechanical Lock Systems ⋮ A note on the parity assignment problem ⋮ A Computationally Efficient Method for Nonparametric Modeling of Neural Spiking Activity with Point Processes ⋮ Minimum Time Multi-UGV Surveillance ⋮ On greedy approximation algorithms for a class of two-stage stochastic assignment problems ⋮ Three-dimensional embedded subband coding with optimized truncation (3-D ESCOT) ⋮ The minimum evolution problem: Overview and classification ⋮ Set covering approach for reconstruction of sibling relationships ⋮ A Fast ℒ_p Spike Alignment Metric ⋮ Tree search algorithm for assigning cooperating UAVs to multiple tasks ⋮ A simplex like approach based on star sets for recognizing convex-\(QP\) adverse graphs ⋮ A survey on graphs with convex quadratic stability number ⋮ A simple effective heuristic for embedded mixed-integer quadratic programming ⋮ Some graph optimization problems with weights satisfying linear constraints ⋮ Cycle-connected mixed graphs and related problems ⋮ Cycle-connected mixed graphs and related problems ⋮ Colloquium: Quantum annealing and analog quantum computation ⋮ On the decidability of finding a positive ILP-instance in a regular set of ILP-instances ⋮ The random fractional matching problem ⋮ Heuristic scheduling of parallel machines with sequence-dependent set-up times ⋮ One line and n points ⋮ On tropical Kleene star matrices and alcoved polytopes ⋮ A commentary on some recent methods in sibling group reconstruction based on set coverings ⋮ Multilevel Algorithms for Acyclic Partitioning of Directed Acyclic Graphs ⋮ Solving LP Relaxations of Some NP-Hard Problems Is As Hard As Solving Any Linear Program ⋮ Knapsack problems in groups ⋮ Weighted popular matchings ⋮ Parametrizing an Integer Linear Program by an Integer ⋮ Unnamed Item ⋮ Finding groups with maximum betweenness centrality ⋮ Approximate core allocations and integrality gap for the bin packing game ⋮ The recurrent method to solve the assignment problem ⋮ Persistency in maximum cardinality bipartite matchings ⋮ Evaluation of solution of discrete optimization problem with incomplete input ⋮ On the minimum number of Steiner points of constrained 1-line-fixed Steiner tree in the Euclidean plane \(\mathbb{R}^2\) ⋮ Irregular polyomino tiling via integer programming with application in phased array antenna design ⋮ Approximation algorithms for solving the constrained arc routing problem in mixed graphs ⋮ Computational complexity of queries based on itemsets ⋮ A lower bound on the expected optimal value of certain random linear programs and application to shortest paths in directed acyclic graphs and reliability ⋮ The power of greedy algorithms for approximating Max-ATSP, cyclic cover, and superstrings ⋮ Approximations for constructing tree-form structures using specific material with fixed length ⋮ Efficient domination through eigenvalues ⋮ Optimal transportation and the falsifiability of incompletely specified economic models ⋮ A linear programming approach to reasoning about probabilities ⋮ A graph theoretic approach to input-to-state stability of switched systems ⋮ Parallel learning of automatic classes of languages ⋮ A proof of the duality of the DINA model and the DINO model ⋮ Fast algorithm to find 2-factor of minimum weight ⋮ On combinatorial optimization problems on matroids with uncertain weights ⋮ A new neighborhood structure for round robin scheduling problems ⋮ Breakout local search for maximum clique problems ⋮ A recurrent algorithm to solve the weighted matching problem ⋮ Optimal discriminating designs for several competing regression models ⋮ Cycle-based reducibility of multi-index transport-type systems of linear inequalities ⋮ Fast integer-valued algorithms for optimal allocations under constraints in stratified sampling ⋮ Reducing the size of combinatorial optimization problems using the operator vaccine by fuzzy selector with adaptive heuristics ⋮ Multicriterial multi-index resource scheduling problems ⋮ Ensemble clustering using factor graph ⋮ Breast cancer prediction using the isotonic separation technique ⋮ The empirical cost of optimal incomplete transportation ⋮ Practical strategies for generating rank-1 split cuts in mixed-integer linear programming ⋮ Semidefinite approximations for quadratic programs over orthogonal matrices ⋮ A new extension of local search applied to the Dial-A-Ride problem ⋮ On imposing connectivity constraints in integer programs ⋮ Complexity results for the basic residency scheduling problem ⋮ Dimension spectra of random subfractals of self-similar fractals ⋮ A robust hybrid method for nonrigid image registration ⋮ A novel probabilistic clustering model for heterogeneous networks ⋮ Fast density-weighted low-rank approximation spectral clustering

This page was built for publication: