  


Algorithms with large domination ratio
Noga Alon (nogamath.tau.ac.il) Abstract: Let $P$ be an optimization problem, and let $A$ be an approximation algorithm for $P$. The domination ratio $\domr(A,n)$ is the maximum real $q$ such that the solution $x(I)$ obtained by $A$ for any instance $I$ of $P$ of size $n$ is not worse than at least a fraction $q$ of the feasible solutions of $I$. We describe a deterministic, polynomial time algorithm with domination ratio $1o(1)$ for the partition problem, and a deterministic, polynomial time algorithm with domination ratio $\Omega(1)$ for the MaxCut problem and for some farreaching extensions of it, including Max$r$Sat, for each fixed $r$. The techniques combine combinatorial and probabilistic methods with tools from Harmonic Analysis. Keywords: Combinatorial Optimization; Domination analysis; Approximation algorithms Category 1: Combinatorial Optimization Citation: Tech. Report Dept of Computer Science Royal Holloway, University of London 0304 Download: [PDF] Entry Submitted: 04/08/2003 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  