Keyword: approximation algorithms

Found 18 papers in total
Mixture surrogate models based on Dempster‐Shafer theory for global optimization problems
Mixture surrogate models based on Dempster‐Shafer theory for global optimization problems
2011,
Recent research in algorithms for solving global optimization problems using response...
Riemannian convexity of functionals
Riemannian convexity of functionals
2011,
This paper extends the Riemannian convexity concept to action functionals defined by...
On the Approximability of Single‐Machine Scheduling with Precedence Constraints
On the Approximability of Single‐Machine Scheduling with Precedence Constraints
2011,
We consider the single‐machine scheduling problem to minimize the weighted sum...
An improved monotone algorithm for scheduling related machines with precedence constraints
An improved monotone algorithm for scheduling related machines with precedence constraints
2011,
We answer an open question posed by Krumke et al. (2008) by showing how to turn the...
A note on the generalized min‐sum set cover problem
A note on the generalized min‐sum set cover problem
2011,
This paper considers the generalized min-sum set cover problem. A 485-approximation...
Approximation Algorithms for the Interval Constrained Coloring Problem
Approximation Algorithms for the Interval Constrained Coloring Problem
2011,
We consider the interval constrained coloring problem, which appears in the...
Reoptimization of the Shortest Common Superstring Problem
Reoptimization of the Shortest Common Superstring Problem
2011,
A reoptimization problem describes the following scenario: given an instance of an...
Approximability of Packing Disjoint Cycles
Approximability of Packing Disjoint Cycles
2011,
Given a graph G , the edge‐disjoint cycle packing problem is to find the...
String matching with inversions and translocations in linear average time (most of the time)
String matching with inversions and translocations in linear average time (most of the time)
2011,
We present an efficient algorithm for finding all approximate occurrences of a given...
Flexible coloring
Flexible coloring
2011,
? We propose a new optimization problem called ‘flexible coloring’....
An Approximation Algorithm for the Minimum Co‐Path Set Problem
An Approximation Algorithm for the Minimum Co‐Path Set Problem
2011,
We present an approximation algorithm for the problem of finding a minimum set of...
Multidimensional Approximation Algorithms for Capacity‐Expansion Problems
Multidimensional Approximation Algorithms for Capacity‐Expansion Problems
2011,
We develop multidimensional balancing algorithms to compute provably...
k‐Outerplanar Graphs, Planar Duality, and Low Stretch Spanning Trees
k‐Outerplanar Graphs, Planar Duality, and Low Stretch Spanning Trees
2011,
Low distortion probabilistic embedding of graphs into approximating trees is an...
New Approximation Algorithms for Minimum Cycle Bases of Graphs
New Approximation Algorithms for Minimum Cycle Bases of Graphs
2011,
We consider the problem of computing an approximate minimum cycle basis of an...
Tight Approximation Ratio of a General Greedy Splitting Algorithm for the Minimum k‐Way Cut Problem
Tight Approximation Ratio of a General Greedy Splitting Algorithm for the Minimum k‐Way Cut Problem
2011,
For an edge‐weighted connected undirected graph, the minimum k ‐way cut...
Scheduling jobs with equal processing times subject to machine eligibility constraints
Scheduling jobs with equal processing times subject to machine eligibility constraints
2011,
We consider the problem of nonpreemptively scheduling a set of n jobs with equal...
Functional optimization by variable‐basis approximation schemes
Functional optimization by variable‐basis approximation schemes
2011,
Functional optimization problems arising in Operations Research are investigated. In...
35/44‐approximation for Asymmetric Maximum TSP with Triangle Inequality
35/44‐approximation for Asymmetric Maximum TSP with Triangle Inequality
2011,
We describe a new approximation algorithm for the asymmetric maximum traveling...
Papers per page: