3

Blum's speedup theorem, proved in 1967, shows that there is such a problem $P$ that has no optimal algorithm. The problem $P$ doesn't look all that much like addition or graph coloring - it's defined in terms of sets of machines $Z_i$, the primitive recursive functions $\phi_i(n)$ computed by the $i$th machine, and "step-counting functions" $\Phi_i(n)$ (...


2

One place where this is approached in an interesting way for a certain class of algorithms and combinatorial problems is in analytic combinatorics. The main approach described is similar to what you suggest: you start with some concrete implementation of an algorithm and identify some repeated operation (typically the heaviest one) that you'll use to ...


1

Here is a link, may be it can help you. http://fc.isima.fr/~nourine/publications.php M. Habib and L. Nourine : A Linear Time Algorithm to Recognize Distributive Lattices, RR LIRMM, No 92-012, 1992.


1

It's certainly possible to simplify the presentation: A graph $G = (V, E)$ A weight function $w_1 : V \mapsto \mathbb{N}$ A weight function $w_2 : E \mapsto (\mathbb{N} \cup \{-\infty\})$. This corresponds to your formulation of $w_2$ as a total function on $V \times V$, where $w_2(x,y) = 0$ if $(x,y) \notin P$, except that $w_2(x,y) = - \infty$ if $(x, y) \...


1

Can this be reformulated as follows (careful, I am sleep-deprived with a cranky toddler in the room): We are looking at a random graph $G$ with 6000 weighted nodes, a subgraph $G'$ induced by about 4000 edges, and 140.000 other weighted edges of positive weight but strictly smaller than the nodes they connect to. A satisfying assignment for $C$ induces a ...


1

It's worth noting that some of the great properties that the stable marriage problem has fail in the hospitals and resident model (many-to-one matching). For example, hospital-proposing differed acceptance is not strategyproof for the hospitals. It's a really useful exercise to come up with an input where this happens. Intuitively, it can occur when a ...


1

Yes, in straightforward ways. To accommodate partial lists, the doctors stop proposing after they've been rejected from every hospital in their order, and remain unmatched. The hospitals automatically reject any proposing doctor who's not in their list, even if it means remaining unmatched. You can picture these as preference lists $h_1 \succeq h_2 \succeq \...


Only top voted, non community-wiki answers of a minimum length are eligible