Computationally Related Problems

DOI10.1137/0203021zbMath0272.68040OpenAlexW1995246641WikidataQ56070240 ScholiaQ56070240MaRDI QIDQ5180395

Publication date: 1975

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0203021

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Turing machines and related notions (03D10)

Related Items

Spectral bounds for the clique and independence numbers of graphs, New LP-based local and global algorithms for continuous and mixed-integer nonconvex quadratic programming, PROCESSOR-TIME-OPTIMAL SYSTOLIC ARRAYS, A complexity theory for feasible closure properties, Topographic Mapping of Large Dissimilarity Data Sets, Integer equal flows, Simulation of discrete linear time-invariant fuzzy dynamic systems, An efficient global algorithm for a class of indefinite separable quadratic programs, And/or-convexity: a graph convexity based on processes and deadlock models, Quadratic programming is in NP, On Approximation Algorithms for Concave Mixed-Integer Quadratic Programming, Weighted Boolean Formula Games, Redundancy in logic. II: 2CNF and Horn propositional formulae, Unnamed Item, Generalized S-lemma and strong duality in nonconvex quadratic programming, Deterministic global optimization in ab-initio quantum chemistry, Tractability, hardness, and kernelization lower bound for and/or graph solution, Multi-market portfolio optimization with conditional value at risk, Revisiting the complexity of and/or graph solution, Robust minimum cost flow problem under consistent flow constraints, Probably approximately optimal satisficing strategies, Optimization via rejection-free partial neighbor search, On tail dependence matrices. The realization problem for parametric families, Indefinite multi-constrained separable quadratic optimization: large-scale efficient solution, A study of piecewise linear-quadratic programs, Approximation of the quadratic set covering problem, Effective algorithms for separable nonconvex quadratic programming with one quadratic and box constraints, Robust transshipment problem under consistent flow constraints, Capacity-preserving subgraphs of directed flow networks, Non deterministic polynomial optimization problems and their approximations, Optimization problems and the polynomial hierarchy, Eigenvalue-based algorithm and analysis for nonconvex QCQP with one constraint, Generalized max flow in series-parallel graphs, A graph theoretic approach to switching function minimization, Compact linearization for binary quadratic problems subject to assignment constraints, ANALYZING VULNERABILITIES OF CRITICAL INFRASTRUCTURES USING FLOWS AND CRITICAL VERTICES IN AND/OR GRAPHS, Computability and randomness of Nash equilibrium in infinite games, Finding optimal satisficing strategies for and-or trees, Deciding non-emptiness of hypergraph languages generated by connection-preserving fusion grammars is NP-complete, A note on integral generalized flows in directed partial 2-trees, Canonical Duality Theory: Connections between Nonconvex Mechanics and Global Optimization, Complexity and algorithms for nonlinear optimization problems, Embedding equality constraints of optimization problems into a quantum annealer, New model and heuristics for safety stock placement in general acyclic supply chain networks, A new algorithm for concave quadratic programming, On the parallel approximability of a subclass of quadratic programming., A convergent conical algorithm with \(\omega \)-bisection for concave minimization, A modified simplicial algorithm for convex maximization based on an extension of \(\omega \)-subdivision, A continuous knapsack problem with separable convex utilities: approximation algorithms and applications, Joint economic production allocation and ordering policies in a supply chain consisting of multiple plants and a single retailer, On approximation algorithms for concave mixed-integer quadratic programming, The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two, Level-planar drawings with few slopes, How to Calculate the Barycenter of a Weighted Graph, Production allocation and shipment policies in a multiple-manufacturer–single-retailer supply chain, Optimal solutions for unrelated parallel machines scheduling problems using convex quadratic reformulations, Learning to Optimize via Posterior Sampling, PROCESSOR LOWER BOUND FORMULAS FOR ARRAY COMPUTATIONS AND PARAMETRIC DIOPHANTINE SYSTEMS, A low and a high hierarchy within NP, Optimal systolic array algorithms for tensor product, Finding a minimum equivalent graph of a digraph, Minimal Disclosure in Hierarchical Hippocratic Databases with Delegation, Comparison of algorithms for simple stochastic games, Exact Worst-Case Performance of First-Order Methods for Composite Convex Optimization