Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Valentin E. Brimkov:

TR03-081 | 10th October 2003
Valentin E. Brimkov, Bruno Codenotti, Valentino Crespi, Reneta Barneva, Mauro Leoncini

Computation of the Lov\'asz Theta Function for Circulant Graphs

The Lov\'asz theta function $\theta(G)$ of a graph $G$ has attracted a lot of attention for its connection with diverse issues, such as communicating without errors and computing large cliques in graphs. Indeed this function enjoys the remarkable property of being computable in polynomial time, despite being sandwitched between clique ... more >>>

TR00-017 | 3rd March 2000
Valentin E. Brimkov, Stefan S. Dantchev

On the Algebraic Complexity of Integer Programming

In the framework of the Blum-Shub-Smale real number model \cite{BSS}, we study the {\em algebraic complexity} of the integer linear programming problem
(ILP$_{\bf R}$) : Given a matrix $A \in {\bf R}^{m \times n}$ and vectors
$b \in {\bf R}^m$, $d \in {\bf R}^n$, decide if there is $x ... more >>>

TR98-015 | 16th January 1998
Valentin E. Brimkov, Stefan S. Dantchev

Lower Bounds, "Pseudopolynomial" and Approximation Algorithms for the Knapsack Problem with Real Coefficients

In this paper we study the Boolean Knapsack problem (KP$_{{\bf R}}$)
$a^Tx=1$, $x \in \{0,1\}^n$ with real coefficients, in the framework
of the Blum-Shub-Smale real number computational model \cite{BSS}.
We obtain a new lower bound
$\Omega \left( n\log n\right) \cdot f(1/a_{\min})$ for the time
complexity ... more >>>

ISSN 1433-8092 | Imprint