Search Results - subject:"approximation algorithms"

Did you mean: subject:"approximation algorithm" (11,480 results)

An approximation algorithm for the bipartite traveling tournament problem

Hoshino, Richard; Kawarabayashi, Ken-ichi - In: Mathematics of operations research 38 (2013) 4, pp. 720-728

Persistent link: https://www.econbiz.de/10010210740

Parameterized complexity of k-anonymity: hardness and tractability

Bonizzoni, Paola; Vedova, Gianluca Della; Dondi, Riccardo; … - In: Journal of combinatorial optimization 26 (2013) 1, pp. 19-43

Persistent link: https://www.econbiz.de/10009757309

Complexity and approximation of the connected set-cover problem

Zhang, Wei; Wu, Weili; Lee, Wonjun; Du, Ding-Zhu - In: Journal of Global Optimization 53 (2012) 3, pp. 563-572

Persistent link: https://www.econbiz.de/10010896437

Approximation algorithms for TTP(2)

Thielen, Clemens; Westphal, Stephan - In: Computational Statistics 76 (2012) 1, pp. 1-20

. We show that the well-known independent lower bound for this case cannot be reached and present two approximation … algorithms for the problem. The first algorithm has an approximation ratio of $${3/2+\frac{6}{n-4}}$$ in the case that n/2 is odd …

Persistent link: https://www.econbiz.de/10010847696

A New Compact Linear Programming Formulation for Choice Network Revenue Management

Kunnumkal, Summit; Talluri, Kalyan - Barcelona Graduate School of Economics (Barcelona GSE) - 2012

The choice network revenue management model incorporates customer purchase behavior as a function of the offered products, and is the appropriate model for airline and hotel network revenue management, dynamic sales of bundles, and dynamic assortment optimization. The optimization problem is a...

Persistent link: https://www.econbiz.de/10010851338

Approximation algorithms for TTP(2)

Thielen, Clemens; Westphal, Stephan - In: Mathematical Methods of Operations Research 76 (2012) 1, pp. 1-20

. We show that the well-known independent lower bound for this case cannot be reached and present two approximation … algorithms for the problem. The first algorithm has an approximation ratio of <InlineEquation ID="IEq1"> <EquationSource Format …

Persistent link: https://www.econbiz.de/10010999722

Approximation algorithms for the parallel flow shop problem

Zhang, Xiandong; van de Velde, Steef - In: European Journal of Operational Research 216 (2012) 3, pp. 544-552

a 127-approximation algorithm. Both these algorithms run in O(nlogn) time. These are the first approximation algorithms …

Persistent link: https://www.econbiz.de/10010577572

Rank-two update algorithms for the minimum volume enclosing ellipsoid problem

Cong, Wei-jie; Liu, Hong-wei; Ye, Feng; Zhou, Shui-sheng - In: Computational Optimization and Applications 51 (2012) 1, pp. 241-257

Persistent link: https://www.econbiz.de/10010998385

Theoretical rate of convergence for interval inclusion functions

Scholz, Daniel - In: Journal of Global Optimization 53 (2012) 4, pp. 749-767

Persistent link: https://www.econbiz.de/10010557856

Computational Complexity, Fairness, and the Price of Anarchy of the Maximum Latency Problem

Correa, Jose R.; Schulz, Andreas S.; Stier Moses, Nicolas E. - Sloan School of Management, Massachusetts Institute of … - 2004

We study the problem of minimizing the maximum latency of flows in networks with congestion. We show that this problem is NP-hard, even when all arc latency functions are linear and there is a single source and sink. Still, one can prove that an optimal flow and an equilibrium flow share a...

Persistent link: https://www.econbiz.de/10005750543