Publication:4739657

zbMath0503.90060MaRDI QIDQ4739657

Christos H. Papadimitriou, Kenneth Steiglitz

Publication date: 1982

zbMATH Keywords

combinatorial optimization; ellipsoid algorithm; NP-completeness; matroids; complexity theory; polynomial time algorithms; network flow problems; shortest path problems; spanning tree problem; matching problems

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

90C10: Integer programming

90C05: Linear programming

90B10: Deterministic network models in operations research

90-01: Introductory exposition (textbooks, tutorial papers, etc.) pertaining to operations research and mathematical programming

Related Items

TSP ejection chains, Measure concentration in optimization, Massively parallel augmenting path algorithms for the assignment problem, On a dynamic auction mechanism for a bilateral assignment problem, An efficient P-D algorithm for shortest path problem, The \(\beta\)-assignment problem in general graphs, A greedy algorithm for the optimal basis problem, Branch and bound methods for scheduling problems with multiprocessor tasks on dedicated processors, Pseudopolynomial algorithms for CTV minimization in single machine scheduling, Can datalog be approximated?, On variations of the subset sum problem, A strongly polynomial algorithm for the inverse shortest arborescence problem, Converting triangulations to quadrangulations, Parallel single grid and multigrid solution of industrial compressible flow problems, Planning of high school examinations in Denmark, Computational complexity of a problem arising in fixed order output feedback design, Rescheduling of identical parallel machines under machine eligibility constraints., Using global search heuristics for the capacity vehicle routing problem., On the robust shortest path problem., A local search template., On the hardness of efficiently approximating maximal non-\(L\) submatrices., On bottleneck assignment problems under categorization., Parallel machine scheduling of machine-dependent jobs with unit-length., Parallel machine scheduling with a common server, Quasi-Hamiltonicity: A series of necessary conditions for a digraph to be Hamiltonian, Heuristic and exact algorithms for the simultaneous assignment problem, Boolean constraint satisfaction: Complexity results for optimization problems with arbitrary weights, Degenerate optimal basis graphs in linear programming, A large step random walk for minimizing total weighted tardiness in a job shop, A simple heuristic for maximizing service of carousel storage, Alternating cycles and trails in \(2\)-edge-coloured complete multigraphs, On the properties of the subsets of a discrete domain defined by the local optimae of a function endowed with some geometrical properties, Performance evaluation of evolutionary class of algorithms -- an application to 0-1 knapsack problem, Formulating logical implications in combinatorial optimisation, A theory of complexity for continuous time systems, Decidability of the consistency problem for regular symbolic picture description languages, A period vehicle routing case study, Experimental results on quadrangulations of sets of fixed points, Relaxed tours and path ejections for the traveling salesman problem, Exact credal treatment of missing data, Length-bounded disjoint paths in planar graphs, Annealed replication: A new heuristic for the maximum clique problem, A framework for the greedy algorithm, Data-independent neighborhood functions and strict local optima, Extended neighborhood: Definition and characterization, Beam-ACO--hybridizing ant colony optimization with beam search: an application to open shop scheduling, On the mean radius of permutation polytopes, Learning local transductions is hard, Matrix permanent inequalities for approximating joint assignment matrices in tracking systems, Single machine scheduling to minimize total weighted tardiness, Generalized measures of association for ranked data with an application to prediction accuracy, The generalized linear complementarity problem and an algorithm to find all its solutions, A forward/reverse auction algorithm for asymmetric assignment problems, Computing the throughput of a network with dedicated lines, Three algorithms for bicriteria integer linear programs, Polynomial auction algorithms for shortest paths, Greedy randomized adaptive search procedures, An identity for matching and skew-symmetric determinant, The plant location problem with demand-dependent setup costs and centralized allocation, Treatment of combinatorial optimization problems using selection equations with cost terms. II: NP-hard three-dimensional assignment problems, Treatment of combinatorial optimization problems using selection equations with cost terms. I: Two-dimensional assignment problems, Team formation: Matching quality supply and quality demand., Containing and shrinking ellipsoids in the path-following algorithm, Fixed edge-length graph drawing is NP-hard, Parametric programming and Lagrangian relaxation: The case of the network problem with a single side-constraint, A data parallel augmenting path algorithm for the dense linear many-to-one assignment problem, Tracking elementary particles near their primary vertex: A combinatorial approach, Subdivision of simplices relative to a cutting plane and finite concave minimization, Intersection reporting on two collections of disjoint sets, ``Global graph problems tend to be intractable, Future paths for integer programming and links to artificial intelligence, A parametric characterization and an \(\epsilon\)-approximation scheme for the minimization of a quasiconcave program, Voronoi diagrams with barriers and on polyhedra for minimal path planning, An algorithm for the multiprocessor assignment problem, A labeling algorithm to solve the assignment problem, Constrained spanning trees and the traveling salesman problem, Least-cost partition algorithms, Cancellativity in finitely presented semigroups, A simple complexity proof for a polynomial-time linear programming algorithm, Computational complexity of optimum multiuser detection, Efficient text fingerprinting via Parikh mapping, Consistency problems in ER-schemas for database systems, Simultaneous mesh generation and partitioning for Delaunay meshes, Extension of M-convexity and L-convexity to polyhedral convex functions, Algorithms for multicast connection under multi-path routing model., Approximation algorithms for fractional knapsack problems, Interior-point methods: Worst case and average case analysis of a phase-I algorithm and a termination procedure., Selecting hierarchical facilities in a service-operations environment, Matching games with partial information, Characterizations of consistent marked graphs, On regular drawn symbolic picture languages, A mathematical model and a solution method for the problem of placing various-sized circles into a strip, Routing algorithm for multicast under multi-tree model in optical networks, Polynomial approximation schemes and exact algorithms for optimum curve segmentation problems, Shortest route computation in distributed systems, A branch-and-bound algorithm for the early/tardy machine scheduling problem with a common due-date and sequence-dependent setup time, Using geometry to solve the transportation problem in the plane, An identity for bipartite matching and symmetric determinant, A new heuristic for the period traveling salesman problem, An inverse problem of the weighted shortest path problem, The complexity of resource allocation and price mechanisms under bounded rationality, Discrete-event dynamic systems: The strictly convex case, A constrained matching problem, A unifying approach to heuristic search, Fusion methods for multiple sensor systems with unknown error densities, Refined proximity and sensitivity results in linearly constrained convex separable integer programming, A primal-dual approximation algorithm for generalized Steiner network problems, Determining functional relationships from trained neural networks, Matroid optimization with generalized constraints, A polyhedron with all \(s-t\) cuts as vertices, and adjacency of cuts, Completeness of vector discrete optimization problems, An auction algorithm for the max-flow problem, Intelligent transportation systems -- Enabling technologies, Cutting planes, connectivity, and threshold logic, Strategies with memories: Local search in an application oriented environment. Applied local search -- a prologue, Strength and adaptability of problem-space based neighborhoods for resource-constrained scheduling, Mathematical problems in cryptology, Complexity of the Frobenius problem, Global optimization for the biaffine matrix inequality problem, Speeding up Karmarkar's algorithm for multicommodity flows, An infeasible-start algorithm for linear programming whose complexity depends on the distance from the starting point to the optimal solution, Primal-dual target-following algorithms for linear programming, Large step volumetric potential reduction algorithms for linear programming, Parallel genetic algorithms with local search, Constrained matroidal bottleneck problems, Reverse search for enumeration, Performances of parallel branch and bound algorithms with best-first search, An \(O(\sqrt {n} L)\) iteration bound primal-dual cone affine scaling algorithm for linear programming, A unifying geometric solution framework and complexity analysis for variational inequalities, Problem space local search for number partitioning, Metaheuristics: A bibliography, An approach for the network flow problem with multiple objectives, A linear time algorithm for maximum matchings in convex, bipartite graphs, Parallel local search, Test driving three 1995 genetic algorithms: New test functions and geometric matching, Maximal irredundant functions, The \(Multi\)-SAT algorithm, Housing market short-term equilibriums maximizing linear utility functions, Algorithms and codes for dense assignment problems: The state of the art, Concerning existential definition of the class \(NP\): Theoretical analysis of an alternative approach, An integer programming problem and rank decomposition of block upper triangular matrices, A simple criterion for structurally fixed modes, On the solution of concave knapsack problems, Finding a complete matching with the maximum product on weighted bipartite graphs, Solving real-life vehicle routing problems efficiently using tabu search, Computational complexity of inner and outer \(j\)-radii of polytopes in finite-dimensional normed spaces, A parametric programming methodology to solve the Lagrangian dual for network problems with multiple side-constraints, Computing the bipartite edge frustration of fullerene graphs, Recent progress on combinatorics and algorithms for low discrepancy roundings, Automatic segmentation of metaphase cells based on global context and variant analysis, Inference in credal networks: Branch-and-bound methods and the A/R+ algorithm, Enriched workflow modelling and stochastic branch-and-bound, On stable least squares solution to the system of linear inequalities, Two phase algorithms for the bi-objective assignment problem, Locating a low-level waste disposal site, On the frontiers of polynomial computations in tropical geometry, On the computational complexity of coalitional resource games, Maxx: Test pattern optimisation with local search over an extended logic, Discrete optimization algorithms and problems of decision making in a fuzzy environment, On a decision procedure for quantified linear programs, How to allocate hard candies fairly, An intelligent agent negotiation strategy in the electronic marketplace environment, Solving 0-1 programming problems by a penalty approach., The minimum shift design problem, Constraint satisfaction methods for solving the staff transfer problem, Shape matching and modeling using skeletal context, Complexity and algorithms for nonlinear optimization problems, A new approach to the learning effect: Beyond the learning curve restrictions, Exploiting semidefinite relaxations in constraint programming, Improved complexity results on solving real-number linear feasibility problems, The routing open-shop problem on a network: complexity and approximation, A PTAS for the minimization of polynomials of fixed degree over the simplex, A constraint programming approach to extract the maximum number of non-overlapping test forms, Algorithms of discrete optimization and their application to problems with fuzzy coefficients, Randomized methods for the number partitioning problem, Eigenvectors of interval matrices over max--plus algebra, A framework for the complexity of high-multiplicity scheduling problems, DNA solution of integer linear programming, Queueing networks of random link topology: stationary dynamics of maximal throughput schedules, Orthogonal drawings of graphs with vertex and edge labels, The logarithmic HLS inequality for systems on compact manifolds, Ant colony optimization theory: a survey, Selfish unsplittable flows, Order preserving reductions and polynomial improving paths, Solving H-horizon, stationary Markov decision problems in time proportional to log (H), The stable set problem and the thinness of a graph, A p2p streaming service architecture with distributed caching, Personal mobility support in future service architectures, The travelling salesman problem: selected algorithms and heuristics†, Dynamic matchings and quasidynamic fractional matchings. II, SOLVING THE TRAVELING SALESMAN PROBLEM USING EFFICIENT RANDOMIZED PARALLEL APPROXIMATION ALGORITHMS, Sensitivity analysis in stochastic flow networks using the Monte Carlo method, Consistency and satisfiability of waveform timing specifications, An efficient heuristic algorithm for minimum matching, A survey of heuristics for the weighted matching problem, Boolean Methods of Optimization over Independence Systems, Optimal dynamic routing in communication networks with continuous traffic, Unlabelled Partition Systems: Optimization and Complexity, A unified framework for off-line permutation routing in parallel networks, Project scheduling under competition, A matching problem in the plane, Concerning the achromatic number of graphs, Linear, quadratic, and bilinear programming approaches to the linear complementarity problem, Games against nature, On negative cycles in mixed graphs, A lower bound to the complexity of Euclidean and rectilinear matching algorithms, The complexity of analog computation, Randomized algorithms in combinatorial optimization: A survey, Scaling algorithms for network problems, Polyhedral proof methods in combinatorial optimization, A condition for the strong regularity of matrices in the minimax algebra, An algorithm for shortest-path motion in three dimensions, The hierarchical network design problem, Complexity of certain decision problems about congruential languages, A shortest augmenting path algorithm for dense and sparse linear assignment problems, A Lagrangean relaxation method for the constrained assignment problem, Representability in mixed integer programming. I: Characterization results, Strong linear independence in bottleneck algebra, Karmarkar's algorithm and the ellipsoid method, Structural analysis of local search heuristics in combinatorial optimization, Scheduling jobs with fixed start and end times, Fractional matchings and the Edmonds-Gallai theorem, Complexity of matching problems, Communication complexity of convex optimization, Minimum cost-reliability ratio path problem, Minimum deviation problems, Probabilistic satisfiability, On finding optimal and near-optimal lineal spanning trees, The general maximum matching algorithm of Micali and Vazirani, Computing the bump number is easy, Communication and its cost in graph-restricted games, The complexity of facets resolved, How easy is local search?, The complexity of recognizing polyhedral scenes, A new dominance procedure for combinatorial optimization problems, A polynomial-time solution to Papadimitriou and Steiglitz's ``traps, Algorithms of placing recovery points, On the efficiency of maximum-flow algorithms on networks with small integer capacities, Decentralized detection by a large number of sensors, Probabilistic construction of deterministic algorithms: approximating packing integer programs, Construction of infinite de Bruijn arrays, Optimal product design using conjoint analysis: Computational complexity and algorithms, Dual coordinate step methods for linear network flow problems, A new approach to choosing initial points in local search, An algorithm for the detection and construction of Monge sequences, Parallel construction of perfect matchings and Hamiltonian cycles on dense graphs, The parallel complexity of finding a blocking flow in a 3-layer network, On the number of steps in proofs, Scheduling unit-time jobs on processors with different capabilities, An extension of Karmarkar's projective algorithm for convex quadratic programming, Local optimization on graphs, Interior path following primal-dual algorithms. I: Linear programming, Interior path following primal-dual algorithms. II: Convex quadratic programming, Single-machine scheduling with learning considerations, On finding a vertex solution using interior point methods, On the complexity of generalized due date scheduling problems, Use of dynamic trees in a network simplex algorithm for the maximum flow problem, Correlation polytopes: Their geometry and complexity, The uniquely solvable bipartite matching problem, Systematic choice of initial points in local search: Extensions and application to neural networks, Temporal constraint networks, An unfeasible matching problem, An \(\varepsilon\)-approximation scheme for combinatorial optimization problems with minimum variance criterion, A fully polynomial time approximation scheme for minimum cost-reliability ratio problems, A note on the approximation of the MAX CLIQUE problem, Finding minimum-cost flows by double scaling, Optimal placement of identical resources in a tree, Weighted graphs and university course timetabling, A weighted min-max relation for intervals, Local minima for indefinite quadratic knapsack problems, Optimal strategies for some team games, Finding approximate solutions to NP-hard problems by neural networks is hard, An arithmetic model of computation equivalent to threshold circuits, Scheduling to minimize weighted earliness and tardiness about a common due-date, Learning in parallel, On players with a bounded number of states, Path-matching problems, Random pseudo-polynomial algorithms for some combinatorial programming problems, The traveling salesman problem: An overview of exact and approximate algorithms, A multiperiod traveling salesman problem: Heuristic algorithms, Traveling salesman problem and local search, On the complexity of scheduling tasks with discrete starting times, Solving combinatorial optimization problems using Karmarkar's algorithm, On affine scaling algorithms for nonconvex quadratic programming, On the convergence of the affine-scaling algorithm, Solving a cutting-stock problem with the constraint logic programming language CHIP, Optimal due-date assignment and sequencing, A pseudo-polynomial algorithm for detecting minimum weighted length paths in a network, A linear time algorithm for graph partition problems, Capacitated lot-sizing and scheduling by Lagrangean relaxation, Global search algorithms for minimum concave-cost network flow problems, Auction algorithms for network flow problems: A tutorial introduction, Stacks, queues, and deques with order-statistic operations, Reasoning about qualitative temporal information, The multicovering problem, A hierarchical algorithm for making sparse matrices sparser, A neural network approach to the traffic control problem in reverse baseline networks, Quantifiers and approximation, Search and sweep numbers of finite directed acyclic graphs, An \(O(\log m)\) parallel algorithm for the minimum spanning tree problem, Approximation algorithms for three-dimensional assignment problems with triangle inequalities, Heuristic solutions and confidence intervals for the multicovering problem, A measure-theoretical max-flow-min-cut problem, A simpler and faster algorithm for optimal total-work-content-power due data determination, A dynamic location problem for graphs, Cyclic orders, Scheduling periodic events, New crash procedures for large systems of linear constraints, Graph properties checkable in linear time in the number of vertices, Approximate solution of NP optimization problems, The smallest networks on which the Ford-Fulkerson maximum flow procedure may fail to terminate, Scheduling on a single processor with variable speed, Knapsack problems for NL, Training digraphs, Interval propagation to reason about sets: Definition and implementation of a practical language, Dynamic algorithms for shortest paths in planar graphs, A genuinely polynomial primal simplex algorithm for the assignment problem, Polynomial algorithms for LP over a subring of the algebraic integers with applications to LP with circulant matrices, Approximation algorithms for indefinite quadratic programming, A primal-dual simplex method for linear programs, Complexity of unification problems with associative-commutative operators, A generalized hypergreedy algorithm for weighted perfect matching, A long-step barrier method for convex quadratic programming, Geometric Knapsack problems, On worst-case aggregation analysis for network location problems, The generic canonical form of a regular structured matrix pencil, A survey of very large-scale neighborhood search techniques, Local ratio with negative weights., Block linear majorants in quadratic 0--1 optimization, Resource allocation under limited sharing, Making sparse matrices sparser: Computational results, A level set algorithm for a class of reverse convex programs, Active set algorithms for isotonic regression; a unifying framework, Approximate algorithms for the Knapsack problem on parallel computers, Recent trends in combinatorial optimization, Network models for vehicle and crew scheduling, Certain NP-complete matching problems, On monotonicity in the scaled potential algorithm for linear programming, Theoretical efficiency of a shifted-barrier-function algorithm for linear programming, On the regularity of matrices in min algebra, Shortest paths without a map, An algorithm of internal feasible directions for linear integer programming, Note on solving linear complementarity problems as jointly constrained bilinear programs, Completeness in approximation classes, An extended ant colony algorithm and its convergence analysis, The nucleolus of balanced simple flow networks, Robust inference of trees, Approximating the minimal sensor selection for supervisory control, An algorithm for projective point matching in the presence of spurious points, ILP approaches to the blockmodel problem, Approximability of single machine scheduling with fixed jobs to minimize total completion time, Neural approach for solving several types of optimization problems, Digraph matrix partitions and trigraph homomorphisms, Direct graph \(k\)-partitioning with a Kernighan-Lin like heuristic, Two due date assignment problems in scheduling a single machine, On ascending Vickrey auctions for heterogeneous objects, Ascending price Vickrey auctions for general valuations, A microfluidic systems-based DNA algorithm for solving special 0-1 integer programming problem, Old and new results on algebraic connectivity of graphs, An effective hybrid algorithm for university course timetabling, Canonical bases in linear programming, On the power of neural networks for solving hard problems, An efficient distributed algorithm for maximum matching in general graphs, The complexity of determinacy problem on group testing, An optimal parallel algorithm for linear programming in the plane, A feasibly constructive lower bound for resolution proofs, k-sum optimization problems, The optimum execution order of queries in linear storage, Blocking versus nonblocking interprocess communication: A note on the effect on concurrency, A geometric consistency theorem for a symbolic perturbation scheme, The auction algorithm for the transportation problem, A state-of-the-art review of parallel-machine scheduling research, An algorithm for linear programming which requires \(O(((m+n)n^ 2+(m+n)^{1.5}n)L)\) arithmetic operations, Low-viscosity lattice gases, Bounds on the size of branch-and-bound proofs for integer knapsacks, The capacitated max \(k\)-cut problem, A general trimming approach to robust cluster analysis, Complexity of local search for the \(p\)-median problem, The single-machine earliness-tardiness scheduling problem with due date assignment and resource-dependent processing times, Forming partnerships in a virtual factory, The Monge-Ampère-Kantorovich approach to reconstruction in cosmology, The general \(\sigma \) all-ones problem for trees, Large gaps in one-dimensional cutting stock problems, A proposal for a hybrid meta-strategy for combinatorial optimization problems, Convergence of a modified algorithm of fast probabilistic modeling, George Dantzig's impact on the theory of computation, On the polyhedral complexity of the integer points in a hyperball, Additivity obstructions for integral matrices and pyramids, A method for approximating pairwise comparison matrices by consistent matrices, Rake linking for suburban train services, An assignment-based heuristic for vehicle routing with time windows, Average case complexity results for a centering algorithm for linear programming problems under Gaussian distributions, The subdivision-constrained minimum spanning tree problem, Dealing with label switching in mixture models under genuine multimodality, A complexity tradeoff in ranking-function termination proofs, The complexity of determining a shortest cycle of even length, The complexity of facets (and some facets of complexity), A successful algorithm for the undirected Hamiltonian path problem, An approach to the subgraph homeomorphism problem, An analysis of a decomposition heuristic for the assignment problem, An approximation algorithm for the asymmetric travelling salesman problem with distances one and two, The maximum benefit Chinese postman problem and the maximum benefit traveling salesman problem, The complexity of some reachability problems for a system on a finite group, Simulated annealing - to cool or not, Lower bounds for sorting of sums, Convex hulls of orbits of representations of finite groups and combinatorial optimization, Effective assignment algorithm for continuous two-stage activities in loading and transportation management, Mechanisms for local search, A heuristic for blocking flow algorithms, A new and improved algorithm for the 3-cut problem, The job shop scheduling problem: Conventional and new solution techniques, Parallel processing for difficult combinatorial optimization problems, General information dispersal algorithms, On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems, Randomized Boolean decision trees: Several remarks, The life span method -- a new variant of local search, A graph theoretical approach for the yield enhancement of reconfigurable VLSI/WSI arrays, Solvability of the vector problem by the linear criteria convolution algorithm, Locating flow-capturing units on a network with multi-counting and diminishing returns to scale, Price-directive decomposition applied to routing in telecommunication networks, Algorithms for network piecewise-linear programs: A comparative study, Routing trains through railway stations: Complexity issues, Formalization of the class of problems solvable by a nondeterministic Turing machine, The complexity of multidimensional periodic scheduling, A \(2_3^2\) superstring approximation algorithm, On the complexity and approximation of syntenic distance, Genotyping of pooled microsatellite markers by combinatorial optimization techniques, Project scheduling under resource and mode identity constraints: Model, complexity, methods, and application, The \(\beta\)-assignment problems, Scheduling under a common due-date on parallel unrelated machines, An optimal tree search method for the manufacturing systems cell formation problem, Improved exploration in Hopfield network state-space through parameter perturbation driven by simulated annealing, A branch and bound algorithm for the resource-constrained project scheduling problem, Classical and new heuristics for the open-shop problem: A computational evaluation, A general approach to solving a wide class of fuzzy optimization problems, Persistency in the assignment and transportation problems, Lexicographic bottleneck combinatorial problems, A branch and bound algorithm for symmetric 2-peripatetic salesman problems, A model for the assignment of candidates to constituencies in a mixed election system, Algorithms for preemptive scheduling of different classes of processors to do jobs with fixed times, Two parallel machine sequencing problems involving controllable job processing times, An overview of median and stack filtering, The knapsack program generator of fractal curves with random stopping rule, Strong regularity of matrices -- a survey of results, Some new results regarding spikes and a heuristic for spike construction, A generic auction algorithm for the minimum cost network flow problem, Parallel primal-dual methods for the minimum cost flow problem, Computation of the solutions of nonlinear polynomial systems, A greedy heuristic for a minimum-weight forest problem, A set covering reformulation of the pure fixed charge transportation problem, Stable marriage and indifference, Tabu search for the job-shop scheduling problem with multi-purpose machines, A quasiconcave minimization method for solving linear two-level programs, Computability, complexity and economics, The auction algorithm: A distributed relaxation method for the assignment problem, Series parallel composition of greedy linear programming problem, Designing secure communication protocols from trust specifications, Approximate kinodynamic planning using \(L_ 2\)-norm dynamic bounds, Approximation algorithms for multi-dimensional assignment problems with decomposable costs, Some results concerning post-infeasibility analysis, Complexity of a class of nonlinear combinatorial problems related to their linear counterparts, An ordered independence system and its applications to scheduling problems, Efficient inference in Bayes networks as a combinatorial optimization problem, Simple characterizations of \(P(\# P)\) and complete problems, The hybrid spanning tree problem, Simulated annealing and tabu search in the long run: A comparison on QAP tasks, Primal-dual algorithms for linear programming based on the logarithmic barrier method, On problems with short certificates, Objects that cannot be taken apart with two hands, A robust heuristic for the generalized assignment problem, Combinatorial optimization techniques for spacecraft scheduling automation, Maximum number of disjoint paths connecting specified terminals in a graph, A bicriterion objective for levelling the schedule of a mixed-model, \(JIT\) assembly process, Some properties of the Hessian of the logarithmic barrier function, Approximating shortest superstrings with constraints, A Lagrangean heuristic for the capacitated concave minimum cost network flow problem, Maximizing the value of a space mission, The traveling salesman problem with delivery and backhauls, Tabu search performance on the symmetric travelling salesman problem, On-line algorithms for weighted bipartite matching and stable marriages, An algorithm for an Eulerian trail traversing specified edges in given order, Polynomial algorithms for linear programming over the algebraic numbers, On the magnetisation of the ground states in two dimensional Ising spin glasses, Asymptotics for transportation cost in high dimensions, Regularity of matrices in min-algebra and its time-complexity, Weighted fractional and integral \(k\)-matching in hypergraphs, New local search approximation techniques for maximum generalized satisfiability problems, A primal-dual interior point method whose running time depends only on the constraint matrix, A note on determining pure-strategy equilibrium points of bimatrix games, Some results on the computational complexity of symmetric connectionist networks., A hypergraph model for constraint logic programming and applications to bus drivers' scheduling, The determinant of a tree's neighborhood matrix, Vertex heaviest paths and cycles in quasi-transitive digraphs, Alternating cycles and paths in edge-coloured multigraphs: A survey, On the core of routing games, Deriving constraints among argument sizes in logic programs, On the solvability problem for equations with a single coefficient, On linear programming and matrix scaling over the algebraic numbers, Inverse matroid intersection problem, A branch \(\&\) bound algorithm for the open-shop problem, Understanding retiming through maximum average-delay cycles, Probabilistic analysis of an enhanced partitioning algorithm for the steiner tree problem in R^d, Ripples, complements, and substitutes in singly constrained monotropic parametric network flow problems, Optimal Matching and Empirical Measures, On the Localization and Computation of Zeros of Bessel Functions, Lower bounds for resolution and cutting plane proofs and monotone computations, Geometric Separators for Finite-Element Meshes, Copositive realxation for genera quadratic programming, Matching Theorems and Empirical Discrepancy Computations using Majorizing Measures, Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : de la structure de NPO à la structure des instances, Unnamed Item, Rights and Decentralized Computation, Approximation algorithms for combinatorial fractional programming problems, A general theory of dual optimization problems. II: On the perturbational dual problem corresponding to an unperturbational dual problem, Design of the ATM-based interconnecting network of the access segment of future cellular systems, Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : formalisme unifié et classes d'approximation, Unnamed Item, A NEW APPROACH TO FINDING OPTIMAL LINEAR SCHEDULES FOR UNIFORM DEPENDENCE ALGORITHMS†, A strongly polynomial algorithm for a new class of linear inequalities¹, Cycles and paths in semicomplete multipartite digraphs, theorems, and algorithms: a survey, A column generation method for inverse shortest path problems, On generalization/specialization for conceptual graphs, Star partitions and the graph isomorphism problem, Off‐line permutation routing on circuit‐switched fixed‐routing networks, The Klee–Minty random edge chain moves with linear speed, Heuristic estimates in shortest path algorithms, Multiplicity and complexity issues in contemporary production scheduling, Experiments on the minimum linear arrangement problem, An Exact Distribution-Free Test Comparing Two Multivariate Distributions based on Adjacency, Weighted bipartite graph for locating optimal LSB substitution for secret embedding, Development of neurofuzzy architecture for solving theN-Queens problem, Une procédure de purification pour les problèmes de complémentarité linéaire, monotones, Unnamed Item, Optimal resource allocation with minimum activation levels and fixed costs, A sum of disjoint products algorithm for reliability evaluation of flow networks, A class of bottleneck expansion problems, Efficient algorithms on distributive lattices, Geometric phase-transition on systems with sparse long-range connections, Local optimality subsets and global optimization: A prospective approach, An approximate algorithm for nonlinear integer programming, Variable neighborhood search: Principles and applications, Polarity-free automatic classification of chromosomes., Iterative state-space reduction for flexible computation, Graph colourings and partitions, Convexity and global optimization: A theoretical link, A faster data assignment algorithm for maximum likelihood-based multitarget motion tracking with bearings-only measurements, Shortest path algorithms using dynamic breadth‐first search, A dynamic tabu search for large-scale generalized assignment problems, Local search algorithms for a single-machine scheduling problem with positive and negative time-lags, Model-based Bayesian feature matching with application to synthetic aperture radar target recognition, Intuitive solution-doubling techniques for worst-case analysis of some survivable network design problems, Load balancing for redundant storage strategies: Multiprocessor scheduling with machine eligibility, An efficient network flow code for finding all minimum cost \(s-t\) cutsets, Models and solution techniques for frequency assignment problems, Matching point features under small nonrigid motion, Performance of linear-space search algorithms, Recognizing when heuristics can approximate minimum vertex covers is complete for parallel access to NP, Unnamed Item, A Bayesian Approach to Simulated Annealing, Linear Time Algorithms to the Minimum All-Ones Problem for Unicyclic and Bicyclic Graphs, A class of bounded approximation algorithms for graph partitioning, RESAMPLING FOR FUZZY CLUSTERING, FREIGHT TRAIN ROUTING AND SCHEDULING IN A PASSENGER RAIL NETWORK: COMPUTATIONAL COMPLEXITY AND THE STEPWISE DISPATCHING HEURISTIC, Optimal Field Splitting, with Applications in Intensity-Modulated Radiation Therapy, Approximating Alternative Solutions, Distributed asynchronous computation of fixed points, A unified framework for primal-dual methods in minimum cost network flow problems, Network design and dynamic routing under queueing demand, Lagrangian relaxation for the star-star concentrator location problem: Approximation algorithm and bounds, A Variable-Complexity Norm Maximization Problem, A Packing Problem You Can Almost Solve by Sitting on Your Suitcase, Affirmative action algorithms, Polyhedral Combinatorics in Combinatorial Optimization, Computing a Sparse Basis for the Null Space, Maintainability of a class of discrete-time systems, On the stability of asynchronous iterative processes, Classifying the computational complexity of problems, The Null Space Problem II. Algorithms, On Minimum Critically n-Edge-Connected Graphs, Packing and covering with integral feasible flows in integral supply-demand networks, The complexity of minimum cut and maximum flow problems in an acyclic network, Polymatroidal flow network models with multiple sinks, Zu einigen Nachbarschaftsstrukturen fiir Iterationsverfahren zur naherangsweisen Lösung spezieller Reihenfolgeprohleme, Designing a minimal spanning tree network subject to a budget constraint, The Fermat-Steiner-Weber-problem in Minkowski spaces, Exact cuts in networks, Simulated annealing: An introduction, A comparison of phase and nonphase network flow algorithms, Some further relations between unperturbational and perturbational dual optimization problems, Characterizing stochastic flow networks using the monte carlo method, Approximate solutions of capacitated fixed-charge minimum cost network flow problems, On a parametric shortest path problem from primal—dual multicommodity network optimization, Solution of combinatorial optimization problems with minimax criterion, Algorithms to construct a mathematical model of preferences using expert judgments, Shortest path problems with node failures, Open shop problems with unit time operations, Exact Solution of Cutting Stock Problems Using Column Generation and Branch-and-Bound, Heuristic scheduling of jobs on a multi-product batch processing machine, An improved iterative reconstruction algorithm for traveltime tomography, A fast algorithm for locating supplying center on a lattice, Hybrid symbiotic genetic optimisation for robust edge-based stereo correspondence, Disjoint pattern database heuristics, Statistical mechanics methods and phase transitions in optimization problems, A simulated annealing approach to police district design, The cable trench problem: Combining the shortest path and minimum spanning tree problems, Two-variable linear programming in parallel, Calculation of exact bounds for the solution set of linear interval systems