PhD Project blog

Papers accepted to SODA 2012

noreply@blogger.com (Oleksandr) — Sun, 18 Sep 2011 05:37:00 +0000

Recently the list of papers accepted to SODA 2012 has appeared. In it there is a paper on progress in TSP "A Proof of the Boyd-Carr Conjecture". According to its abstract, "Boyd and Carr [3] observe that we do not even know the worst-case upper bound on the ratio of the optimal 2-matching to the subtour LP; they conjecture the ratio is at most 10/9."

Making further Progress in Approximating graphic TSP

noreply@blogger.com (Oleksandr) — Sat, 06 Aug 2011 06:43:00 +0000

Another work concerning approximation of graphic TSP appeared recently. It improves analysis of Moemke and Svensson from $1.461$ to $1.458$ and makes it cleaner.

NP-complete problem which is neither NP-complete in the strong sense nor solvable by pseudopolynomial algorithms?

noreply@blogger.com (Oleksandr) — Sun, 17 Jul 2011 07:38:00 +0000

Recently I've posted on cstheory a question that is described in the title of this post. Since then I've received only one comment and one answer. I think the possible answer to it can be a list of NP-complete problems in the ordinary sense such that no pseudopolynomial algorithm is known for them.

Another approximation for Graphic TSP below 3/2

noreply@blogger.com (Oleksandr) — Sun, 17 Apr 2011 11:51:00 +0000

Today I've found out that T. Moemke and O. Svensson have made available on the net preprint "Approximating Graphic TSP by Matchings" with new approximation for Graphic TSP below 3/2. It should be mentioned that nearly 5 months ago there have appeared similar result: "A Randomized Rounding Approach to the Traveling Salesman Problem".

Multiobjective Optimization Complexity

noreply@blogger.com (Oleksandr) — Tue, 12 Apr 2011 16:55:00 +0000

Yesterday, there was uploaded an interesting paper on Multiobjective Optimization Complexity, called "The Complexity of Solving Multiobjective Optimization Problems and its Relation to Multivalued Functions". Authors of the paper describe results concerning complexity of different notions of "what it means to 'solve the problem'". For all this notions they define corresponding complexity classes and prove results on (non)equivalence of some of these new classes to such classes as $\mathbb{NP}$ or $\mathbb{NPMV}_g$, where $\mathbb{NPMV}_g$ is the complexity "class of multivalued functions whose graph is in $\mathbb{P}$".

People sometimes say “X is true.” A rule to discover if this statement makes any sense is ...

noreply@blogger.com (Oleksandr) — Sat, 26 Feb 2011 19:43:00 +0000

Though Richard Lipton wanted to tell eventually about that it's unknown whether Euclidean TSP is NP-complete/belongs to NP I liked the rule of his advisor:

People sometimes say “X is true.” A rule to discover if this statement makes any sense is to think about the statement: “X is false.” If the later is silly or obvious, then the original statement made no sense.

[1102.3766] Derandomizing HSSW Algorithm for 3-SAT

noreply@blogger.com (Oleksandr) — Mon, 21 Feb 2011 11:42:00 +0000

In their paper the authors write: "we obtain an $O(1.3303^n)$-time deterministic algorithm for 3-SAT, which is currently fastest."

Timeline of computer science

noreply@blogger.com (Oleksandr) — Fri, 11 Feb 2011 17:41:00 +0000

In the above-named post by Scott Aaronson I've found some (many?) new things for myself, especially I liked the mention of the first paper on nondeterminism.

NEXP does not have non-uniform quasi-polynomial-size ACC circuits of $o(\log\log n)$ depth

noreply@blogger.com (Oleksandr) — Wed, 09 Feb 2011 11:32:00 +0000

The author, Fengming Wang, a third year Ph.D. student at Rutgers, states his result as:

In this paper, we show that Williams’ lower bound result can be extended to
a broader class of ACC circuits with non-constant depth. A function $f$ is a quasipolynomial if $f = n^{\log^{O(1)}n}$.

How do you get a “Physical Intuition” for results in TCS?

noreply@blogger.com (Oleksandr) — Wed, 09 Feb 2011 01:53:00 +0000

Nice answers for a nice question. I especially liked the ones by Ryan Williams, Hsien-Chih Chang 張顯之 and Jukka Suomela.

A CS Professor's blog: Some old advice from Andy Yao

noreply@blogger.com (Oleksandr) — Mon, 31 Jan 2011 17:12:00 +0000

A very helpful advice from Andrew Yao.

Dominance rules and combinatorial optimization

noreply@blogger.com (Oleksandr) — Sat, 29 Jan 2011 20:34:00 +0000

Today I've found a very interesting review by Antoine Jouglet and Jacque Carlier about dominance rules. The paper gives definition and a thorough classification of dominance rules. Essentialy, a dominance rule can be viewed as any rule which allows cut off some part of solution space guaranteeing that at least one optimum is left. Dominant subset is a subset obtained by applying some dominance rule. Widely-known dominant subsets of schedules in schedulig theory are semiactive, active and nondelay schedules. One example of nondelay schedules is the schedules generated by well-known list scheduling algorithm for $P|prec|C_{max}$.

New lower bounds for one dimensional bin packing

noreply@blogger.com (Oleksandr) — Fri, 28 Jan 2011 19:44:00 +0000

Today the paper on lower bounds for bin packing from the last WAOA has been published. The authors of the paper improve on the old (good?) lower bound of van Vliet $1.54014\dots$ to $\frac{248}{161}=1.54037\dots$. They also give a combinatorial proof of van Vliet's bound. Other case they consider is improved lower bounds for decreasing list online bin packing. The technique used in proofs is packing pattern technique from [1], additionally, new series of instances is introduced instead of Sylvester sequence.

Galambos, G.: A 1.6 Lower Bound for the Two-dimensional On-line Rectangle Bin Packing. Acta Cybernetica 10, 21–24 (1991).

Fixed Job Sequence problems

noreply@blogger.com (Oleksandr) — Sat, 22 Jan 2011 00:47:00 +0000

I've found a very interesting paper "Coupled-Task Scheduling on a Single Machine Subject
to a Fixed Job Sequence". The essence of their study is about how hard is it to find an optimum if on the jobs of the instance the linear order is fixed. Interestingly, the authors propose only algorithms but no proofs of NP-hardness. In the paper precedence relation is defined as follows:

"given a fixed job sequence, if job $J_i$ precedes job $J_j$ in the specified sequence, then it is required to schedule the tasks such that $a_i$ precedes $a_j$, and $b_i$ precedes $b_j$."

Speed-Price Equilibrium « Algorithmic Game-Theory/Economics

noreply@blogger.com (Oleksandr) — Thu, 20 Jan 2011 14:16:00 +0000

I think that's a good idea to tell students about such applications of economics and algorithmic game theory, in particular.

The Geomblog: The 5+5 Commandments of a Ph.D.

noreply@blogger.com (Oleksandr) — Wed, 12 Jan 2011 15:44:00 +0000

Some advice on pusuing Ph.D.

[1011.1157] Sorting by Transpositions is Difficult

noreply@blogger.com (Oleksandr) — Wed, 05 Jan 2011 01:20:00 +0000

Sorting by Transpositions is Hard.

11011110: Top ten algorithms preprints of 2010

noreply@blogger.com (Oleksandr) — Fri, 31 Dec 2010 21:08:00 +0000

Top ten algorithms preprints of 2010 from the point of view of David Eppstein.

Hitler and P = NP

noreply@blogger.com (Oleksandr) — Wed, 29 Dec 2010 14:37:00 +0000

Computational Complexity: Complexity Year in Review 2010

noreply@blogger.com (Oleksandr) — Wed, 29 Dec 2010 14:25:00 +0000

Major happenings in Complexity Theory this (2010) year.

The paper on "Improved Algorithm for Metric TSP" is available now!

noreply@blogger.com (Oleksandr) — Sat, 25 Dec 2010 15:53:00 +0000

Here.

Computational Complexity: BREAKTHROUGH in algorithms: Improved algorithm for Metric TSP!!!!!!!!

noreply@blogger.com (Oleksandr) — Mon, 20 Dec 2010 17:46:00 +0000

I'm looking forward to see this in arxiv asap.

The short description of the result by one of the authors can be found here.

[1012.3319] A note about a partial no-go theorem for quantum PCP

noreply@blogger.com (Oleksandr) — Thu, 16 Dec 2010 02:53:00 +0000

Interesting paper on the possibility of quantum PCP.

The Recognition of Triangle Graphs

noreply@blogger.com (Oleksandr) — Thu, 16 Dec 2010 01:02:00 +0000

Interesting to note is that: "since triangle and simple-triangle graphs lie naturally between permutation and trapezoid graphs, and since they share a very similar structure with them, it was expected that the recognition of triangle and simple-triangle graphs is polynomial, as it is also the case for permutation and trapezoid graphs. In this article we surprisingly prove that the recognition of triangle graphs is NP-hard, even in the case where the input graph is known to be a trapezoid graph."

Dr. Wortman’s top resources for trends in Computer Science — The Pollak Library Blog

noreply@blogger.com (Oleksandr) — Thu, 09 Dec 2010 01:56:00 +0000

Basic information resources for CS scientist.