scientific article; zbMATH DE number 3793772

Kenneth Steiglitz, Christos H. Papadimitriou

Publication date: 1982

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

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

Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) Linear programming (90C05) Deterministic network models in operations research (90B10) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to operations research and mathematical programming (90-01)

Related Items

Interior-point methods: Worst case and average case analysis of a phase-I algorithm and a termination procedure., Length-bounded disjoint paths in planar graphs, Annealed replication: A new heuristic for the maximum clique problem, A framework for the greedy algorithm, Analysis of FPTASes for the multi-objective shortest path problem, An effective iterated tabu search for the maximum bisection problem, Exact and heuristic approaches based on noninterfering transmissions for joint gateway selection, time slot allocation, routing and power control for wireless mesh networks, 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, Single machine scheduling with resource allocation and learning effect considering the rate-modifying activity, Can datalog be approximated?, On variations of the subset sum problem, A strongly polynomial algorithm for the inverse shortest arborescence problem, An exact algorithm to extend lifetime through roles allocation in sensor networks with connectivity constraints, 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., A new adaptive Hungarian mating scheme in genetic algorithms, On the complexity of the unit commitment problem, Tiers for peers: a practical algorithm for discovering hierarchy in weighted networks, Disruption recovery at airports: integer programming formulations and polynomial time algorithms, Generalized probabilistic satisfiability, The complexity landscape of decompositional parameters for ILP, The resource dependent assignment problem with a convex agent cost function, Dual bounds of a service level assignment problem with applications to efficient pricing, On a class of branching problems in broadcasting and distribution, Heuristic approaches for the optimal wiring in large scale robotic skin design, Linear combinations of heuristics for examination timetabling, 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, Probabilistic spatio-temporal knowledge bases: capacity constraints, count queries, and consistency checking, Binary sparse phase retrieval via simulated annealing, A new distributed approximation algorithm for the maximum weight independent set problem, 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, Parallel machine scheduling with a common server, Cancellativity in finitely presented semigroups, A simple complexity proof for a polynomial-time linear programming algorithm, Computational complexity of optimum multiuser detection, Quasi-Hamiltonicity: A series of necessary conditions for a digraph to be Hamiltonian, Efficient text fingerprinting via Parikh mapping, Consistency problems in ER-schemas for database systems, 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, Simultaneous mesh generation and partitioning for Delaunay meshes, Extension of M-convexity and L-convexity to polyhedral convex functions, 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, Algorithms for multicast connection under multi-path routing model., 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, Approximation algorithms for fractional knapsack problems, 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, 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, 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, Sums of idempotents and logarithmic residues in zero pattern matrix algebras, Hybrid constructive heuristics for the critical node problem, Weighted digraphs and tropical cones, Representations of votes facilitating monotonicity-based ranking rules: from votrix to votex, Repairing high school timetables with polymorphic ejection chains, The NPO-completeness of the longest Hamiltonian cycle problem, Near-optimal nonapproximability results for some \textsc{Npo} PB-complete problems, On the empirical scaling of run-time for finding optimal solutions to the travelling salesman problem, Minimum distance index for complex valued ICA, Single machine scheduling with two competing agents and equal job processing times, An alternative approach for proving the NP-hardness of optimization problems, Robust optimization of the 0-1 knapsack problem: balancing risk and return in assortment optimization, Mining approximate interval-based temporal dependencies, A nonmonotone GRASP, A rescheduling and cost allocation mechanism for delayed arrivals, Constant factor approximation algorithm for TSP satisfying a biased triangle inequality, Interpretable clustering using unsupervised binary trees, Graph properties checkable in linear time in the number of vertices, The capacity expansion path problem in networks, Unit commitment in oligopolistic markets by nonlinear mixed variable programming, New perspectives in VLSI design automation: deterministic packing by sequence pair, A hybrid search method for the vehicle routing problem with time windows, Multitask \(n\)-vehicle exploration problem: complexity and algorithm, Decomposition representations of logical equations in problems of inversion of discrete functions, An effective multilevel tabu search approach for balanced graph partitioning, Minimizing the total completion time in single-machine scheduling with aging/deteriorating effects and deteriorating maintenance activities, On the asymptotic behavior of subtour-patching heuristics in solving the TSP on permuted Monge matrices, Algorithmic paradigms for stability-based cluster validity and model selection statistical methods, with applications to microarray data analysis, Stochastic global optimization as a filtering problem, Guarding a set of line segments in the plane, Approximation algorithms for a geometric set cover problem, Local search: is brute-force avoidable?, Scheduling with job-dependent learning effects and multiple rate-modifying activities, Scheduling with learning effects and/or time-dependent processing times to minimize the weighted number of tardy jobs on a single machine, Timetable construction: the algorithms and complexity perspective, The design and implementation of an interactive course-timetabling system, Minimum energy control and optimal-satisfactory control of Boolean control network, Exploring the tractability border in epistemic tasks, Optimal portfolio allocation under the probabilistic VaR constraint and incentives for financial innovation, Computational complexity of convoy movement planning problems, Unrelated parallel-machine scheduling problems with aging effects and deteriorating maintenance activities, Approximate solution of NP optimization problems, The smallest networks on which the Ford-Fulkerson maximum flow procedure may fail to terminate, Minimizing maximum weight of subsets of a maximum matching in a bipartite graph, Scheduling on a single processor with variable speed, Knapsack problems for NL, Training digraphs, Unrelated parallel machine scheduling -- perspectives and progress, Nash equilibria in the two-player kidney exchange game, Interval propagation to reason about sets: Definition and implementation of a practical language, Resource constrained scheduling with general truncated job-dependent learning effect, Automatic construction of parallel portfolios via algorithm configuration, Disturbance rejection control based on state-reconstruction and persistence disturbance estimation, 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, Scheduling with job-rejection and position-dependent processing times on proportionate flowshops, 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, Globally solving a nonlinear UAV task assignment problem by stochastic and deterministic optimization approaches, The generic canonical form of a regular structured matrix pencil, A survey of very large-scale neighborhood search techniques, Due-window assignment and scheduling with multiple rate-modifying activities under the effects of deterioration and learning, Weighted argument systems: basic definitions, algorithms, and complexity results, Local ratio with negative weights., Tropical linear maps on the plane, Block linear majorants in quadratic 0--1 optimization, Bicriteria problems to minimize maximum tardiness and due date assignment cost in various scheduling environments, Solving constrained combinatorial optimization problems via importance sampling in the grand canonical ensemble, A new look at the automatic synthesis of linear ranking functions, Optimal search path for service in the presence of disruptions, 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, Hybrid evolutionary fuzzy learning scheme in the applications of traveling salesman problems, Unrelated parallel-machine scheduling with deterioration effects and deteriorating multi-maintenance activities for minimizing the total completion time, Approximation algorithms for three-dimensional assignment problems with triangle inequalities, Using Approximation Algorithms to Build Evidence Factors and Related Designs for Observational Studies, 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, An optimization model and a solution algorithm for the many-to-many car pooling problem, 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, Robust inference of trees, Geometric algorithms for finding a point in the intersection of balls, Note on the time complexity of resource constrained scheduling with general truncated job-dependent learning effect, Zonotopes and the LP-Newton method, Optimal due date assignment in multi-machine scheduling environments, Max algebraic powers of irreducible matrices in the periodic regime: an application of cyclic classes, Improved algorithm for the symmetry number problem on trees, Classification of applied methods of combinatorial optimization, Cluster analysis for portfolio optimization, Algorithmic properties of ciliate sequence alignment, 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, A spectral-multiplicity-tolerant approach to robust graph matching, Lagrangian bounds from decision diagrams, 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, Using combinatorial optimization in model-based trimmed clustering with cardinality constraints, Some theoretical challenges in digital geometry: a perspective, Polynomial ring automorphisms, rational \((w,\sigma )\)-canonical forms, and the assignment problem, Variable neighborhood search for the cost constrained minimum label spanning tree and label constrained minimum spanning tree problems, A unified approach for scheduling with convex resource consumption functions using positional penalties, Correlation based networks of equity returns sampled at different time horizons, A graphical realization of the dynamic programming method for solving NP-hard combinatorial problems, Optimal due date assignment and resource allocation in a group technology scheduling environment, A novel iterative shape from focus algorithm based on combinatorial optimization, ``Product partition and related problems of scheduling and systems reliability: computational complexity and approximation, 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, Parallel ILP for distributed-memory architectures, Computing and minimizing the relative regret in combinatorial optimization with interval data, GRAFT, a complete system for data fusion, A survey on metaheuristics for stochastic combinatorial optimization, Greedily constructing maximal partial \(f\)-factors, On the design of correct and optimal dynamical systems and games, On visualization scaling, subeigenvectors and Kleene stars in max algebra, Subclasses of solvable problems from classes of combinatorial optimization problems, Using a greedy random adaptative search procedure to solve the cover printing problem, A primal-dual simplex algorithm for bi-objective network flow problems, Hybridizing exact methods and metaheuristics: a taxonomy, Interactive construction of graphical decision models based on causal mechanisms, Asymptotics of the minimum manipulating coalition size for positional voting rules under impartial culture behaviour, A memetic algorithm for graph coloring, 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, A matching problem in the plane, Concerning the achromatic number of graphs, Linear, quadratic, and bilinear programming approaches to the linear complementarity problem, An algorithm of internal feasible directions for linear integer programming, Note on solving linear complementarity problems as jointly constrained bilinear programs, Games against nature, Completeness in approximation classes, On negative cycles in mixed graphs, An extended ant colony algorithm and its convergence analysis, A lower bound to the complexity of Euclidean and rectilinear matching algorithms, The nucleolus of balanced simple flow networks, 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, 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, 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, Selecting hierarchical facilities in a service-operations environment, ParadisEO-MO: from fitness landscape analysis to efficient local search algorithms, 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, 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, Routing algorithm for multicast under multi-tree model in optical networks, Computing the bipartite edge frustration of fullerene graphs, 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, Complexity and approximation of open shop scheduling to minimize the makespan: a review of models and approaches, 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, On the complexity of dynamic mechanism design, 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, Single-machine multitasking scheduling with job efficiency promotion, 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, Single-machine scheduling and slack due-date assignment with aging effect and deteriorating maintenance, The stochastic shortest path problem: a polyhedral combinatorics perspective, A novel kernel correlation model with the correspondence estimation, Locality preserving matching, Streaming graph computations with a helpful advisor, A branch-and-bound approach to the optimization of redundant software under failure correlation, Greed is good for deterministic scale-free networks, Analysis of cluster damages in network systems, Models and methods for solving the problem of network vulnerability, 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, Local search with a SAT oracle for combinatorial optimization, A review of two network curvature measures, On the maximum size of Erdős-Ko-Rado sets in \(H(2d+1, q^2)\), Minimum vertex cover in ball graphs through local search, Mixture model modal clustering, Minimizing the average searching time for an object within a graph, Dynamic temporal decoupling, A simple criterion for structurally fixed modes, On factorization invariants and Hilbert functions, ETSAP-TIAM: The TIMES integrated assessment model. I: Model structure, Rank decomposition under zero pattern constraints and \(\mathsf{L}\)-free directed graphs, Maximum shortest path interdiction problem by upgrading edges on trees under weighted \(l_1\) norm, Fuzzy self-tuning differential evolution for optimal product line design, Complexity analysis of an assignment problem with controllable assignment costs and its applications in scheduling, On the solution of concave knapsack problems, Sequential decision model for inference and prediction on nonuniform hypergraphs with application to knot matching from computational forestry, Range assignment of base-stations maximizing coverage area without interference, A two-step method for solving vector optimization problems on permutation configuration, Mathematical studies of the dynamics of finite-size binary neural networks: a review of recent progress, On the number of solutions to a system of Boolean equations, An efficient algorithm of dead-end controls for solving combinatorial optimization problems, Flexible quantile contour estimation for multivariate functional data: beyond convexity, Boosting isomorphic model filtering with invariants, A theoretical and computational equilibria analysis of a multi-player kidney exchange program, On the number of solutions to linear Diophantine equation and Frobenius problem, Towards an efficient resolution of printing problems, Consistency techniques for polytime linear global cost functions in weighted constraint satisfaction, On time-optimal trajectories in non-uniform mediums, IMPACT OF TOPOLOGY ON THE MAXIMUM MULTICAST THROUGHPUT IN COMMUNICATION NETWORKS WITH NETWORK CODING, Recent progress on combinatorics and algorithms for low discrepancy roundings, New algorithms for pattern matching with wildcards and length constraints, Harmonious coloring: parameterized algorithms and upper bounds, Automorphisms of projective K3 surfaces with minimum entropy, Adaptive tabu search for course timetabling, Single-machine due-window assignment and scheduling with job-dependent aging effects and deteriorating maintenance, Harmonious Coloring: Parameterized Algorithms and Upper Bounds, Integer Programming: Optimization and Evaluation Are Equivalent, Solving H-horizon, stationary Markov decision problems in time proportional to log (H), 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, The stable set problem and the thinness of a graph, A p2p streaming service architecture with distributed caching, Algorithms for solving the symmetry number problem on trees, Identification of video subsequence using bipartite graph matching, Minimum K-Adjacent Rectangles of Orthogonal Polygons and its Application, Consistency and satisfiability of waveform timing specifications, A class of bounded approximation algorithms for graph partitioning, Matching formulation of the staff transfer problem: meta-heuristic approaches, An efficient heuristic algorithm for minimum matching, The cardinality constrained inverse center location problems on tree networks with edge length augmentation, Two results on slime mold computations, A study of complexity transitions on the asymmetric traveling salesman problem, Epsilon-transformation: exploiting phase transitions to solve combinatorial optimization problems, New variable neighborhood search method for minimum sum coloring problem on simple graphs, RESAMPLING FOR FUZZY CLUSTERING, Hybrid Metaheuristics: An Introduction, The complexity of searching implicit graphs, 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, Determining the interset distance, Generalized probabilistic satisfiability and applications to modelling attackers with side-channel capabilities, A combined analytical, numerical, and experimental study of shape-memory-alloy helical springs, On the complexity of optimal hotlink assignment, Focused jump-and-repair constraint handling for fixed-parameter tractable graph problems closed under induced subgraphs, Enriched workflow modelling and stochastic branch-and-bound, New bounds and algorithms for the transshipment yard scheduling problem, On the Relative Complexity of 15 Problems Related to 0/1-Integer Programming, Exact and Parameterized Algorithms for (k, i)-Coloring, OBDD-Based Load Shedding Algorithm for Power Systems, Mixing time and simulated annealing for the stochastic cellular automata, A combinatorial algorithm for Horn programs, Single-machine common flow allowance scheduling with job-dependent aging effects and a deteriorating maintenance activity, 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, A Resampling Approach to Cluster Validation, Maxx: Test pattern optimisation with local search over an extended logic, Discrete optimization algorithms and problems of decision making in a fuzzy environment, Improved Approximations for Hard Optimization Problems via Problem Instance Classification, 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, A survey of heuristics for the weighted matching 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, The travelling salesman problem: selected algorithms and heuristics†, Exploiting semidefinite relaxations in constraint programming, Boolean Methods of Optimization over Independence Systems, Optimal dynamic routing in communication networks with continuous traffic, Improved complexity results on solving real-number linear feasibility problems, Dynamic matchings and quasidynamic fractional matchings. II, Unlabelled Partition Systems: Optimization and Complexity, The routing open-shop problem on a network: complexity and approximation, Personal mobility support in future service architectures, 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, A unified framework for off-line permutation routing in parallel networks, Algorithms of discrete optimization and their application to problems with fuzzy coefficients, On the computational complexity of combinatorial flexibility problems, Project scheduling under competition, Recognizing when heuristics can approximate minimum vertex covers is complete for parallel access to NP, Experimental Study on Approximation Algorithms for Guarding Sets of Line Segments, Approximation Algorithms for the Single Robot Line Coverage Problem, THE NP-HARDNESS OF MINIMIZING THE TOTAL LATE WORK ON AN UNBOUNDED BATCH MACHINE, Unnamed Item, Adjusted Interval Digraphs, Randomized methods for the number partitioning problem, A Bayesian Approach to Simulated Annealing, 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, SOLVING THE TRAVELING SALESMAN PROBLEM USING EFFICIENT RANDOMIZED PARALLEL APPROXIMATION ALGORITHMS, Selfish unsplittable flows, Order preserving reductions and polynomial improving paths, A new mathematical model for tiling finite regions of the plane with polyominoes, Linear Time Algorithms to the Minimum All-Ones Problem for Unicyclic and Bicyclic Graphs, Sensitivity analysis in stochastic flow networks using the Monte Carlo method, SCHEDULING POSITION-BASED DETERIORATING JOBS WITH MULTIPLE RATE-MODIFYING ACTIVITIES AND PAST-SEQUENCE-DEPENDENT DELIVERY TIMES, Network design and dynamic routing under queueing demand, Lagrangian relaxation for the star-star concentrator location problem: Approximation algorithm and bounds, Design of the ATM-based interconnecting network of the access segment of future cellular systems, Off‐line permutation routing on circuit‐switched fixed‐routing networks, Some further relations between unperturbational and perturbational dual optimization problems, A Variable-Complexity Norm Maximization Problem, A Packing Problem You Can Almost Solve by Sitting on Your Suitcase, The Klee–Minty random edge chain moves with linear speed, Space-sweep algorithms for parametric optimization, Parallel and sequential approximation of shortest superstrings, Improved length bounds for the shortest superstring problem, Characterizing stochastic flow networks using the monte carlo method, Approximate solutions of capacitated fixed-charge minimum cost network flow problems, Minimum weight euclidean matching and weighted relative neighborhood graphs, Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : formalisme unifié et classes d'approximation, Understanding retiming through maximum average-delay cycles, Unnamed Item, Affirmative action algorithms, On a parametric shortest path problem from primal—dual multicommodity network optimization, A NEW APPROACH TO FINDING OPTIMAL LINEAR SCHEDULES FOR UNIFORM DEPENDENCE ALGORITHMS†, A Lexicographic 0.5-Approximation Algorithm for the Multiple Knapsack Problem, Probabilistic analysis of an enhanced partitioning algorithm for the steiner tree problem in R^d, Solution of combinatorial optimization problems with minimax criterion, Algorithms to construct a mathematical model of preferences using expert judgments, On Some Special Network Flow Problems: The Shortest Path Tour Problems, A strongly polynomial algorithm for a new class of linear inequalities¹, Ripples, complements, and substitutes in singly constrained monotropic parametric network flow problems, Cycles and paths in semicomplete multipartite digraphs, theorems, and algorithms: a survey, Optimal Matching and Empirical Measures, Shortest path problems with node failures, A column generation method for inverse shortest path problems, On genuinely time bounded computations, Lower bounds for the matrix chain ordering problem, On generalization/specialization for conceptual graphs, Graph layout problems, On the complexity of incremental computation, Approximation algorithms for a genetic diagnostics problem, Polyhedral Combinatorics in Combinatorial Optimization, Open shop problems with unit time operations, Star partitions and the graph isomorphism problem, Computing a Sparse Basis for the Null Space, Maintainability of a class of discrete-time systems, Unnamed Item, Approximating Alternative Solutions, On the stability of asynchronous iterative processes, A spectral method to detect community structure based on distance modularity matrix, Exact and heuristic approaches for the maximum lifetime problem in sensor networks with coverage and connectivity constraints, 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, Nonnegative Matrix Factorization with Rank Regularization and Hard Constraint, A 2/3-Approximation Algorithm for Vertex Weighted Matching in Bipartite Graphs, Designing a minimal spanning tree network subject to a budget constraint, On the Localization and Computation of Zeros of Bessel Functions, The Fermat-Steiner-Weber-problem in Minkowski spaces, Primal-dual approximation algorithms for integral flow and multicut in trees, with applications to matching and set cover, atalog: A logic language for expressing search and optimization problems, EVOLUTIONARILY-FRAGMENTED ALGORITHM FOR FINDING A MAXIMAL FLAT PART OF A GRAPH, ABOUT THE CONP-COMPLETE “INJECTIVE KNAPSACK” PROBLEM, THE TRAVELING SALESMAN PROBLEM: APPROXIMATE ALGORITHM BY BRANCH-AND-BOUND METHOD WITH GUARANTEED PRECISION, Lower bounds for resolution and cutting plane proofs and monotone computations, The complexity of searching succinctly represented graphs, The travelling salesman and the PQ-tree, Contrasting Evidence Within and Between Institutions That Provide Treatment in an Observational Study of Alternate Forms of Anesthesia, A Complex-Networks View of Hard Combinatorial Search Spaces, Exact cuts in networks, Two-variable linear programming in parallel, SCHEDULING WITH POSITION-BASED DETERIORATING JOBS AND MULTIPLE DETERIORATING RATE-MODIFYING ACTIVITIES, Simulated annealing: An introduction, A comparison of phase and nonphase network flow algorithms, Geometric Separators for Finite-Element Meshes, Copositive realxation for genera quadratic programming, Rights and Decentralized Computation, Optimality parsing and local cost functions in Discontinuous Grammar, Heuristic estimates in shortest path algorithms, Multiplicity and complexity issues in contemporary production scheduling, Matching Theorems and Empirical Discrepancy Computations using Majorizing Measures, On matroids and hierarchical graphs, Approximating shortest superstrings with constraints, Reoptimization of Traveling Salesperson Problems: Changing Single Edge-Weights, Unnamed Item, Experiments on the minimum linear arrangement problem, Random multi-index matching problems, Optimization and testing in linear non‐Gaussian component analysis, Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : de la structure de NPO à la structure des instances, 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, Bipartite Perfect Matching is in Quasi-NC, Optimal Tradeoffs in Matched Designs Comparing US-Trained and Internationally Trained Surgeons, Exact Solution of Cutting Stock Problems Using Column Generation and Branch-and-Bound, Distributed asynchronous computation of fixed points, Heuristic scheduling of jobs on a multi-product batch processing machine, An improved iterative reconstruction algorithm for traveltime tomography, A unified framework for primal-dual methods in minimum cost network flow problems, A fast algorithm for locating supplying center on a lattice, Meaningful and Meaningless Statements in Landscape Ecology and Environmental Sustainability, Flow-Based Algorithms for Improving Clusters: A Unifying Framework, Software, and Performance, Factorizations of the same length in abelian monoids, Algorithm unions for solving discrete optimization problems, On computing discretized Ricci curvatures of graphs: local algorithms and (localized) fine-grained reductions, A note on due-date assignment scheduling with job-dependent learning effects and convex resource allocation, Globally optimal univariate spline approximations, Single-machine Scheduling Problems with Aging/Deteriorating Effect under an Optional Maintenance Activity Consideration, Speedup the optimization of maximal closure of a node-weighted directed acyclic graph, Complexity and approximation for discriminating and identifying code problems in geometric setups, Feasible rounding based diving strategies in branch-and-bound methods for mixed-integer optimization, Non-oblivious local search for graph and hypergraph coloring problems, Construction of a technologically feasible cutting with pierce points placement constraints, Mathematical aspects of the Digital Annealer's simulated annealing algorithm, Concurrent flows and packet routing in Cayley graphs (Preliminary version), A new perspective on single-machine scheduling problems with late work related criteria, SPT optimality (mostly) via linear programming, On measuring inconsistency in definite and indefinite databases with denial constraints, Operational causality -- necessarily sufficient and sufficiently necessary, Canadian traveller problem with predictions, Unsupervised learning on U.S. weather forecast performance, The single robot line coverage problem: Theory, algorithms, and experiments, Mathematics of computation through the lens of linear equations and lattices, Unnamed Item, Unnamed Item, When polynomial approximation meets exact computation, Discriminating Codes in Geometric Setups, 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, Hybrid symbiotic genetic optimisation for robust edge-based stereo correspondence, When can graph hyperbolicity be computed in linear time?, 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, Performance of linear-space search algorithms, Calculation of exact bounds for the solution set of linear interval systems, Scheduling dedicated jobs with variative processing times, Maximum bipartite matchings with low rank data: locality and perturbation analysis, Performance of linear-space search algorithms, The temporal explorer who returns to the base, 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, The Complexity of Contracts, Self-configuring Nature Inspired Algorithms for Combinatorial Optimization Problems, Unnamed Item, A Simple Algorithm for Finding a Non-negative Basic Solution of a System of Linear Algebraic Equations, Solving Linear Programming Problems by Reducing to the Form with an Obvious Answer