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

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, Max-algebra: The linear algebra of combinatorics?, Robust two-stage combinatorial optimization problems under convex second-stage cost uncertainty, The fastest itinerary in time-dependent decentralized travel information systems, LTL receding horizon control for finite deterministic systems, A linear time algorithm for shortest cyclic cover of strings, On stability of discrete-time switched systems, Computationally efficient MIP formulation and algorithms for European day-ahead electricity market auctions, An algorithm with parameterized complexity of constructing the optimal schedule for the routing open shop problem with unit execution times, Characteristic function games with restricted agent interactions: core-stability and coalition structures, Holographic quantum error-correcting codes: toy models for the bulk/boundary correspondence, On the connectivity preserving minimum cut problem, Using expert knowledge in solving the seismic inverse problem, Design of microvascular flow networks using multi-objective genetic algorithms, Efficient algorithms for scheduling parallel jobs with interval constraints in clouds, A decision procedure for linear ``big O equations, Learning parallel portfolios of algorithms, Heuristics for planning with penalties and rewards formulated in logic and computed through circuits, Evolutionary operators for the Hamiltonian completion problem, D-Wave and predecessors: From simulated to quantum annealing, Classes of linear programs solvable by coordinate-wise minimization, Multiple view semi-supervised dimensionality reduction, Maximum margin partial label learning, The symmetric travelling salesman problem. I: New fast lower bounds for the problem of optimal 2-matching, On the implementation of a global optimization method for mixed-variable problems, Complexity of evolution in maximum cooperative P systems, Parallel batch scheduling with nested processing set restrictions, COVID-19: metaheuristic optimization-based forecast method on time-dependent bootstrapped data, Multi-hop sensor network scheduling for optimal remote estimation, Colourful components in \(k\)-caterpillars and planar graphs, Motion planning algorithms for the Dubins Travelling Salesperson Problem, Recoverable robust spanning tree problem under interval uncertainty representations, Robust recoverable and two-stage selection problems, Identifying influential links to control spreading of epidemics, Reinforcement learning for combinatorial optimization: a survey, A pseudo-polynomial algorithm for optimal capacitor placement on electric power distribution networks, LLL-reduction for integer knapsacks, Global discriminative-based nonnegative spectral clustering, Hybrids of Constructive Metaheuristics and Constraint Programming: A Case Study with ACO, Approximating combinatorial optimization problems with the ordered weighted averaging criterion, Parameterized exact and approximation algorithms for maximumk-set cover and related satisfiability problems, On Chubanov's Method for Linear Programming, Deterministic algorithms for compiling quantum circuits with recurrent patterns, Scheduling jobs with sizes and delivery times on identical parallel batch machines, Efficient algorithms for scheduling equal-length jobs with processing set restrictions on uniform parallel batch machines, Approximations for two variants of the Steiner tree problem in the Euclidean plane \(\mathbb R^2\), A linear time approximation scheme for scheduling unbounded batch machines with delivery times and inclusive processing set restrictions, Contention-resolving model predictive control for coupled control systems with a shared resource, Integer points in knapsack polytopes and \(s\)-covering radius, Output Rate Variation Problem: Some Heuristic Paradigms and Dynamic Programming, Probably partially true: satisfiability for Łukasiewicz infinitely-valued probabilistic logic and related topics, A linear assignment approach for the least-squares protein morphing problem, Integer programming ensemble of temporal relations classifiers, Topologically trivial closed walks in directed surface graphs, Consistency checking and querying in probabilistic databases under integrity constraints, Hamiltonicity of regular graphs and blocks of consecutive ones in symmetric matrices, The big-M method with the numerical infinite \(M\), Maximum shortest path interdiction problem by upgrading edges on trees under Hamming distance, The stable marriage problem: an interdisciplinary review from the physicist's perspective, Combinatorial two-stage minmax regret problems under interval uncertainty, Transfer affinity propagation-based clustering, Thresholds for extreme orientability, The component model for elementary landscapes and partial neighborhoods, Coupled map lattices as spatio-temporal fitness functions: Landscape measures and evolutionary optimization, Approximation algorithms for constructing some required structures in digraphs, Logistics scheduling with batching and transportation, No sublogarithmic-time approximation scheme for bipartite vertex cover, Sources of complexity in subset choice, Steady states in the scheduling of discrete-time systems, The complexity of maximum matroid--greedoid intersection and weighted greedoid maximiza\-tion, Safe projections of binary data sets, An NP-completeness result of edge search in graphs, A randomized algorithm for the min-Max selecting items problem with uncertain weights, An improved version of the augmented \(\varepsilon\)-constraint method (AUGMECON2) for finding the exact Pareto set in multi-objective integer programming problems, Church's thesis meets the \(N\)-body problem, An efficient algorithm for deciding vanishing of Schubert polynomial coefficients, Solving interval linear least squares problems by PPS-methods, Good (K-means) clusterings are unique (up to small perturbations), Neighbourhood generation mechanism applied in simulated annealing to job shop scheduling problems, A semidefinite programming based polyhedral cut and price approach for the maxcut problem, MDSM: microarray database schema matching using the Hungarian method, Scheduling jobs with release and delivery times subject to nested eligibility constraints, Efficient generation of performance bounds for a class of traffic scheduling problems, Sensor networks and cooperative control, Selection of priority areas in research and development, Theoretical and computational advances for network diversion, Bundling all shortest paths, A triangulation and fill-reducing initialization procedure for the simplex algorithm, The Complexity of the Nucleolus in Compact Games, On the Complexity of Clustering with Relaxed Size Constraints, A note on submodularity preserved involving the rank functions, Exact computation of censored least absolute deviations estimator, Approximation algorithms for solving the line-capacitated minimum Steiner tree problem, Optimizing MSE for clustering with balanced size constraints, Principles of cost minimisation in wireless networks, Optimal security liquidation algorithms, A time-triggered dimension reduction algorithm for the task assignment problem, Combinatorial Optimization Over Two Random Point Sets, Exploring search space trees using an adapted version of Monte Carlo tree search for combinatorial optimization problems, Optimization and sustainable development, Short-term scheduling of production fleets in underground mines using CP-based LNS, 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, Using the WOWA operator in robust discrete optimization problems, A new approximation algorithm for the unbalanced min \(s\)-\(t\) cut problem, Inductive synthesis of cover-grammars with the help of ant colony optimization, Computing the least-core and nucleolus for threshold cardinality matching games, Approximation algorithms for scheduling jobs with release times and arbitrary sizes on batch machines with non-identical capacities, Local equivalences of distances between clusterings -- a geometric perspective, Models and algorithms to improve earthwork operations in road design using mixed integer linear programming, Kernel technology to solve discrete optimization problems, Probabilistic satisfiability: algorithms with the presence and absence of a phase transition, On the complexity of clustering with relaxed size constraints in fixed dimension, A school bus scheduling problem, Efficient local search algorithms for known and new neighborhoods for the generalized traveling salesman problem, Multiple UAV coalitions for a search and prosecute mission, A review of multiobjective programming and its application in quantitative psychology, Gromov-Wasserstein distances and the metric approach to object matching, Clustering Boolean tensors, On the complexity of core, kernel, and bargaining set, Seeking global edges for traveling salesman problem in multi-start search, An algorithm for curve identification in the presence of curve intersections, Threshold protocols in survivor set systems, Anomalous scaling of the optimal cost in the one-dimensional random assignment problem, Combinatorial optimization problems with uncertain costs and the OWA criterion, An adaptive multi-policy grid service for biological sequence comparison, Matrices commuting with a given normal tropical matrix, Unsupervised feature selection based on kernel Fisher discriminant analysis and regression learning, A method of improving initial partition of Fiduccia-Mattheyses algorithm, Estimation of the dimensions of some Kisin varieties, Continuous representations and functional extensions in combinatorial optimization, Production-process optimization algorithm: application to fed-batch bioprocess, Branch-and-bound algorithms: a survey of recent advances in searching, branching, and pruning, Stochastic dominance-based rough set model for ordinal classification, Finding a bounded mixed-integer solution to a system of dual network inequalities, Parallel batch scheduling with inclusive processing set restrictions and non-identical capacities to minimize makespan, The generalized vertex cover problem and some variations, Approximation algorithms for multiple terminal, Hamiltonian path problems, The coordination of transportation and batching scheduling, Quantitative evaluation of time-dependent Petri nets and applications to biochemical networks, Interval scheduling on related machines, Permutation betting markets: singleton betting with extra information, Chips on wafers, or packing rectangles into grids, A hybrid heuristic algorithm for the open-pit-mining operational planning problem, Random weighting, asymptotic counting, and inverse isoperimetry, Complexity of interval minmax regret scheduling on parallel identical machines with total completion time criterion, Parallel machine scheduling with nested processing set restrictions and job delivery times, Solving a real constraint satisfaction model for the university course timetabling problem: a case study, The one-to-one shortest-path problem: An empirical analysis with the two- tree Dijkstra algorithm, The \(k\)-assignment polytope, A Lagrangian-based algorithm for a multiple depot, multiple traveling salesmen problem, Optimization of a peer-to-peer system for efficient content replication, The minimum spanning tree problem with fuzzy costs, Probabilistic weak simulation is decidable in polynomial time, Joint object placement and node dimensioning for internet content distribution, Quasi-polynomials, linear Diophantine equations and semi-linear sets, The bandpass problem: Combinatorial optimization and library of problems, Choosing robust solutions in discrete optimization problems with fuzzy costs, Some methods for evaluating the optimality of elements in matroids with ill-known weights, Interval-parameter optimization problems on graphs, Optimization with randomized search heuristics -- the (A)NFL theorem, realistic scenarios, and difficult functions., A least-squares primal-dual algorithm for solving linear programming problems, Towards an analytic framework for analysing the computation time of evolutionary algorithms, The stochastic location-assignment problem on a tree